{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Encode String with Shortest Length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: encode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #编码最短长度的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>非空</strong> 字符串，将其编码为具有最短长度的字符串。</p>\n",
    "\n",
    "<p>编码规则是：<code>k[encoded_string]</code>，其中在方括号 <code>encoded_string</code><em> </em>中的内容重复 <code>k</code> 次。</p>\n",
    "\n",
    "<p><strong>注：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><em>k</em> 为正整数</li>\n",
    "\t<li>如果编码的过程不能使字符串缩短，则不要对其进行编码。如果有多种编码方式，返回 <strong>任意一种</strong> 即可</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaa\"\n",
    "<strong>输出：</strong>\"aaa\"\n",
    "<strong>解释：</strong>无法将其编码为更短的字符串，因此不进行编码。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaaaa\"\n",
    "<strong>输出：</strong>\"5[a]\"\n",
    "<strong>解释：</strong>\"5[a]\" 比 \"aaaaa\" 短 1 个字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaaaaaaaaa\"\n",
    "<strong>输出：</strong>\"10[a]\"\n",
    "<strong>解释：</strong>\"a9[a]\" 或 \"9[a]a\" 都是合法的编码，和 \"10[a]\" 一样长度都为 5。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aabcaabcd\"\n",
    "<strong>输出：</strong>\"2[aabc]d\"\n",
    "<strong>解释：</strong>\"aabc\" 出现两次，因此一种答案可以是 \"2[aabc]d\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abbbabbbcabbbabbbc\"\n",
    "<strong>输出：</strong>\"2[2[abbb]c]\"\n",
    "<strong>解释：</strong>\"abbbabbbc\" 出现两次，但是 \"abbbabbbc\" 可以编码为 \"2[abbb]c\"，因此一种答案可以是 \"2[2[abbb]c]\"。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 150</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [encode-string-with-shortest-length](https://leetcode.cn/problems/encode-string-with-shortest-length/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [encode-string-with-shortest-length](https://leetcode.cn/problems/encode-string-with-shortest-length/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aaa\"', '\"aaaaa\"', '\"aaaaaaaaaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        encoded_string = ''\n",
    "\n",
    "        for s in strs:\n",
    "            encoded_string += s.replace(\"/\", \"//\") + \"/:\"\n",
    "        return encoded_string\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        decoded_strings = []\n",
    "\n",
    "        current_string = \"\"\n",
    "\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i:i+2] == '//':\n",
    "                current_string += '/'\n",
    "                i += 2\n",
    "            elif s[i:i+2] == \"/:\":\n",
    "                decoded_strings.append(current_string)\n",
    "                current_string = \"\"\n",
    "                i += 2\n",
    "            else:\n",
    "                current_string += s[i]\n",
    "                i += 1\n",
    "        return decoded_strings\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return strs\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '#$%^&'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split('#$%^&')\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:             \n",
    "        return chr(257).join(strs)       \n",
    "    def decode(self, s: str) -> List[str]:        \n",
    "        return s.split(chr(257))\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '[]&&'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split('[]&&')\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    '''\n",
    "    Prefix every string with its length - denoted by a 2-digit hex number.\n",
    "    Time complexity: O(n). \n",
    "    Space complexity: O(1) (neglecting the output string). Explanation: join() pre-computes the length of the string using O(1) space, allocates the required space, and constructs the string.\n",
    "    '''\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return ''.join(f'{len(s):02x}{s}' for s in strs)\n",
    "\n",
    "    '''\n",
    "    Decode.\n",
    "    Time complexity: O(n). Space complexity: O(1).\n",
    "    '''\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        strs = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            length = int(s[i:i+2], 16)\n",
    "            strs.append(s[i+2:i+2+length])\n",
    "            i += 2 + length\n",
    "        return strs\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: [str]) -> str:\n",
    "        \"\"\"将字符串列表编码为单个字符串。\n",
    "\n",
    "        参数:\n",
    "            strs ([str]): 要编码的字符串列表。\n",
    "\n",
    "        返回:\n",
    "            str: 编码后的字符串。\n",
    "        \"\"\"\n",
    "        list_ = []  # 初始化空列表用于存储编码后的字符串\n",
    "        for i in strs:\n",
    "            # 对每个字符串，添加一个四字符长的长度信息（右对齐，不足部分用空格填充），然后将长度信息和字符串拼接\n",
    "            list_.append('{:4}'.format(len(i)) + i)\n",
    "        return ''.join(list_)  # 将所有编码后的字符串拼接为一个字符串并返回\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> [str]:\n",
    "        \"\"\"将单个编码字符串解码为字符串列表。\n",
    "\n",
    "        参数:\n",
    "            s (str): 要解码的字符串。\n",
    "\n",
    "        返回:\n",
    "            [str]: 解码后的字符串列表。\n",
    "        \"\"\"\n",
    "        index = 0  # 初始化索引用于遍历编码字符串\n",
    "        list_ = []  # 初始化空列表用于存储解码后的字符串\n",
    "        while index <= len(s) - 2:\n",
    "            # 从编码字符串中读取四字符长的长度信息，并转换为整数\n",
    "            char_long = int(s[index:index + 4])\n",
    "            # 根据长度信息提取相应的字符串，并添加到列表\n",
    "            list_.append(s[index + 4:index + char_long + 4])\n",
    "            # 更新索引，移动到下一个编码字符串的长度信息处\n",
    "            index += 4 + char_long\n",
    "        return list_  # 返回解码后的字符串列表\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return chr(258)\n",
    "        \n",
    "        return chr(258).join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split(chr(258))\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    # Use 4 bytes as header to indicate the length of string.\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        for s in strs:\n",
    "            length = str(len(s))\n",
    "            header = \"0\" * (4 - len(length)) + length\n",
    "            res.append(header)\n",
    "            res.append(s)\n",
    "        return \"\".join(res)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        read = 0\n",
    "        res = []\n",
    "        while read < n:\n",
    "            header = s[read:read+4]\n",
    "            read += 4\n",
    "            res.append(s[read:read+int(header)])\n",
    "            read += int(header)\n",
    "        return res\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:       \n",
    "        return \"(!@#)\".join(strs)       \n",
    "    def decode(self, s: str) -> List[str]:        \n",
    "        return s.split(\"(!@#)\")\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '%00%'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split('%00%')\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return \"#-#\".join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split(\"#-#\")\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "    def encode(self, strs: List[str]):\n",
    "        #if not strs:\n",
    "        #    return chr(257)\n",
    "        return chr(259).join(strs)\n",
    "        \n",
    "    def decode(self, s):\n",
    "        #if s == chr(257):\n",
    "        #    return []\n",
    "        return s.split(chr(259))\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: [str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        list_ = []\n",
    "        for i in strs:\n",
    "            list_.append('{:4}'.format(len(i)) + i)\n",
    "        return ''.join(list_)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> [str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        index = 0\n",
    "        list_ = []\n",
    "        while index <= len(s) - 2:\n",
    "            char_long = int(s[index:index + 4])\n",
    "            list_.append(s[index + 4:index + char_long + 4])\n",
    "            index += 4 + char_long\n",
    "        return list_\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))\n",
    "\"\"\"\n",
    "作者：青碧凝霜\n",
    "链接：https://leetcode.cn/problems/encode-and-decode-strings/solutions/1010639/python3-ji-lu-fa-by-qing-bi-ning-shuang-z6mi/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs):\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "\n",
    "        ans = ''\n",
    "        ans += str(len(strs))\n",
    "        ans += ':'\n",
    "\n",
    "        for ss in strs:\n",
    "            ans += str(len(ss))\n",
    "            ans += '/'\n",
    "\n",
    "        ans += ''.join(strs)\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    def decode(self, s):\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "\n",
    "        \n",
    "\n",
    "        len_of_list = 0\n",
    "        lens = []\n",
    "\n",
    "        i = 0\n",
    "        tmp = ''\n",
    "        while s[i] != ':':\n",
    "            tmp += s[i]\n",
    "            i += 1\n",
    "\n",
    "        len_of_list = int(tmp)\n",
    "        i += 1\n",
    "\n",
    "        for _ in range(len_of_list):\n",
    "            tmp = ''\n",
    "            while s[i] != '/':\n",
    "                tmp += s[i]\n",
    "                i += 1\n",
    "            lens.append(int(tmp))\n",
    "            i += 1\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for ll in lens:\n",
    "            ans.append(s[i:i+ll])\n",
    "            i += ll\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "####################\n",
    "# class Codec:\n",
    "#     def encode(self, strs: List[str]) -> str:\n",
    "#         \"\"\"Encodes a list of strings to a single string.\n",
    "#         \"\"\"\n",
    "#         ans1 = str(len(strs)) + '#'\n",
    "#         ans2 = ''\n",
    "#         for s in strs:\n",
    "#             ans1 += str(len(ans2)) + '#'\n",
    "#             ans2 += s\n",
    "\n",
    "#         # print(ans1 + ans2)\n",
    "#         return ans1 + ans2\n",
    "        \n",
    "\n",
    "#     def decode(self, s: str) -> List[str]:\n",
    "#         \"\"\"Decodes a single string to a list of strings.\n",
    "#         \"\"\"\n",
    "#         s_list = s.split('#')\n",
    "#         len_s_list = len(s_list)\n",
    "\n",
    "#         n = int(s_list[0])\n",
    "#         id_list = []\n",
    "#         for i in range(n):\n",
    "#             id_list.append(int(s_list[i + 1]))\n",
    "        \n",
    "#         if n + 2 == len_s_list:\n",
    "#             ss = s_list[-1]\n",
    "#         else:\n",
    "#             ss = '#'.join(s[n + 1:])\n",
    "#         # print(ss)\n",
    "\n",
    "#         ans = []\n",
    "#         for i in range(len(id_list) - 1):\n",
    "#             ans.append(ss[id_list[i]: id_list[i + 1]])\n",
    "        \n",
    "#         print(id_list, i)\n",
    "#         # print(id_list[i+1])\n",
    "#         ans.append(ss[id_list[i+1]:]) \n",
    "        \n",
    "#         return ans\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# # Your Codec object will be instantiated and called as such:\n",
    "# # codec = Codec()\n",
    "# # codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 官1：非ascii字符来识别字符为空的情况(unichr函数，python3废弃--无法调试成功)\n",
    "# class Codec:\n",
    "#     def encode(self, strs):\n",
    "#         \"\"\"Encodes a list of strings to a single string.\n",
    "#         :type strs: List[str]\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         if len(strs) == 0: \n",
    "#             # return unichr(258) ### python-2 有unichr函数\n",
    "#             return chr(258)\n",
    "        \n",
    "#         # encode here is a workaround to fix BE CodecDriver error\n",
    "#         # return unichr(257).join(x.encode('utf-8') for x in strs)\n",
    "#         return chr(257).join(x.encode('utf-8') for x in strs)\n",
    "        \n",
    "\n",
    "#     def decode(self, s):\n",
    "#         \"\"\"Decodes a single string to a list of strings.\n",
    "#         :type s: str\n",
    "#         :rtype: List[str]\n",
    "#         \"\"\"\n",
    "#         # if s == unichr(258): \n",
    "#         #     return []\n",
    "#         # return s.split(unichr(257))\n",
    "\n",
    "#         if s==chr(258):return []\n",
    "#         return s.split(chr(257))\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))\n",
    "\n",
    "# 官1：网友py3版\n",
    "class Codec:\n",
    "    def encode(self,strs):\n",
    "        if len(strs)==0:\n",
    "            return chr(258)\n",
    "\n",
    "        return chr(257).join(strs)\n",
    "\n",
    "    def decode(self,s):\n",
    "        if s==chr(258): return []\n",
    "        return s.split(chr(257))\n",
    "\n",
    "# 官2：基于http1.1使用的编码，不依赖与输入字符集\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return chr(256).join(x for x in strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split(chr(256))\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, strs):\n",
    "        \"\"\"\n",
    "        Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        # Join all strings in the list with a separator.\n",
    "        # Each string is prefixed with its length and a separator.\n",
    "        return ''.join(f'{len(s):04d}{s}' for s in strs)\n",
    "\n",
    "    def decode(self, s):\n",
    "        \"\"\"\n",
    "        Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        # Initialize an empty list to store the decoded strings\n",
    "        strs = []\n",
    "        # Initialize a pointer to the start of the string\n",
    "        i = 0\n",
    "        # Loop until the end of the string is reached\n",
    "        while i < len(s):\n",
    "            # Read the length of the next string from the next 4 characters\n",
    "            length = int(s[i:i + 4])\n",
    "            # Move the pointer past the length prefix\n",
    "            i += 4\n",
    "            # Extract the next string using the length prefix\n",
    "            strs.append(s[i:i + length])\n",
    "            # Move the pointer to the start of the next string\n",
    "            i += length\n",
    "        return strs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        res=[]\n",
    "        for word in strs:\n",
    "            res.append(word)\n",
    "            res.append(\"好\")\n",
    "        return \"\".join(res)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        res=[]\n",
    "        pre=\"\"\n",
    "        for ch in s:\n",
    "            if ch!=\"好\":\n",
    "                pre=pre+ch\n",
    "            else:\n",
    "                res.append(pre)\n",
    "                pre=\"\"\n",
    "        return res\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "    def encode(self, strs: List[str]):\n",
    "        if not strs:\n",
    "            return chr(258)\n",
    "        return chr(257).join(strs)\n",
    "        \n",
    "    def decode(self, s):\n",
    "        if s == chr(258):\n",
    "            return []\n",
    "        return s.split(chr(257))\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return chr(258)\n",
    "        return chr(257).join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        if len(s) == chr(258):\n",
    "            return []\n",
    "        return s.split(chr(257))\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '%00%'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split('%00%')\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: [str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\"\"\"\n",
    "        if not strs:\n",
    "            return chr(258)\n",
    "        return chr(257).join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> [str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\"\"\"\n",
    "        if s == chr(258):\n",
    "            return []\n",
    "        return s.split(chr(257))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '%00%'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split('%00%')\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, strs):\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return ''.join(map(lambda s: f\"{len(s)}#{s}\", strs))\n",
    "        #这个匿名函数（或lambda函数）接收一个字符串s作为输入，然后返回一个新的字符串，该字符串首先包含s的长度（len(s)），接着是一个#字符，最后是s本身。\n",
    "        #map函数接收一个函数和一个可迭代对象（在这里是字符串列表strs），并返回一个迭代器，该迭代器为strs中的每个元素应用该函数。在这个例子中，对strs中的每个字符串s，map都应用前面描述的lambda函数，生成一个新的字符串，形式为\"<长度>#<原始字符串>\"。\n",
    "        #''.join(iterable)方法接收一个可迭代对象（通常是一个字符串列表或迭代器）并将其元素连接成一个单一的字符串。\n",
    "\n",
    "    def decode(self, s):\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        i = 0\n",
    "\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while s[j] !='#':\n",
    "                j += 1 #寻找到#号\n",
    "            length = int(s[i:j]) #切片到长度元素\n",
    "            i = j + 1 #j后面第一位是str开始的第一位\n",
    "            j = i +length #str第一位加上长度得到str的最后一位索引\n",
    "            res.append(s[i:j]) #或许str到res中\n",
    "            i = j #继续寻找一下一个str\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        res=[]\n",
    "        for word in strs:\n",
    "            res.append(word)\n",
    "            res.append(\"好\")\n",
    "        return \"\".join(res)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        res=[]\n",
    "        pre=\"\"\n",
    "        for ch in s:\n",
    "            if ch!=\"好\":\n",
    "                pre=pre+ch\n",
    "            else:\n",
    "                res.append(pre)\n",
    "                pre=\"\"\n",
    "        return res\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return chr(258)\n",
    "        return chr(257).join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        if s == chr(258):\n",
    "            return []\n",
    "        return s.split(chr(257))\n",
    "        \n",
    "#编码时：\n",
    "#使用chr(257)来作为分隔符\n",
    "\n",
    "#解码时：\n",
    "#使用chr(257)，然后s.split()来转换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return chr(258)\n",
    "        \n",
    "        return chr(257).join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        if s == chr(258):\n",
    "            return []\n",
    "        \n",
    "        return s.split(chr(257))\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return \"*:*;\".join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split(\"*:*;\")\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        for s in strs:\n",
    "            res.append(\"{:4d}\".format(len(s)))\n",
    "            res.append(s)\n",
    "        return \"\".join(res)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        idx, n = 0, len(s)\n",
    "        while idx < n:\n",
    "            length = int(s[idx: idx + 4])\n",
    "            res.append(s[idx + 4: idx + 4 + length])\n",
    "            idx += 4 + length\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "    def encode(self, strs: List[str]):\n",
    "        if not strs:\n",
    "            return chr(257)\n",
    "        return chr(259).join(strs)\n",
    "        \n",
    "    def decode(self, s):\n",
    "        if s == chr(257):\n",
    "            return []\n",
    "        return s.split(chr(259))\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '%00%'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split('%00%')\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return json.dumps(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return json.loads(s)\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        encoded_str = ''\n",
    "        for s in strs:\n",
    "            encoded_str += str(len(s)) + '#' + s\n",
    "        return encoded_str\n",
    "        \n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        decoded_strs = []\n",
    "        idx = 0\n",
    "        while idx < len(s):\n",
    "            hash_idx = s.find('#', idx)\n",
    "            str_len = int(s[idx:hash_idx])\n",
    "            decoded_strs.append(s[hash_idx+1:hash_idx+1+str_len])\n",
    "            idx = hash_idx + 1 + str_len\n",
    "        return decoded_strs\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs):\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(strs) == 0: \n",
    "            return chr(258)\n",
    "        \n",
    "        # encode here is a workaround to fix BE CodecDriver error\n",
    "        return chr(257).join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s):\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if s == chr(258): \n",
    "            return []\n",
    "        return s.split(chr(257))\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = ''\n",
    "        for s in strs:\n",
    "            res += str(len(s)) + '#' + s \n",
    "        return res \n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        i = 0 \n",
    "        while i < len(s):\n",
    "            j = i \n",
    "            while s[j] != '#':\n",
    "                j += 1\n",
    "            length = int(s[i:j])\n",
    "            res.append(s[j + 1:j + 1 + length])\n",
    "            i = j + 1 + length \n",
    "        return res \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        ans = \"\"\n",
    "        for s in strs:\n",
    "            ans += str(len(s)) + '#' + s\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while s[j] != \"#\":\n",
    "                j += 1\n",
    "            \n",
    "            length = int(s[i:j])\n",
    "            ans.append(s[j+1:j+1+length])\n",
    "\n",
    "            i = j+length+1\n",
    "        return ans\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '|'.join([s.replace('|', '\\\\|') for s in strs])\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        tmp = \"\"\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            c = s[i]\n",
    "            if c == '|':\n",
    "                ret.append(tmp)\n",
    "                tmp = \"\"\n",
    "                i += 1\n",
    "            elif c == '\\\\' and i + 1 < len(s) and s[i + 1] == '|':\n",
    "                tmp += '|'\n",
    "                i += 2\n",
    "            else:\n",
    "                tmp += c\n",
    "                i += 1\n",
    "        ret.append(tmp)\n",
    "        return ret\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        temp = ''\n",
    "        for s in strs:\n",
    "            n = str(len(s))\n",
    "            temp += (4-len(n))*'0' + n\n",
    "            temp += s\n",
    "        return temp\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        strs = []\n",
    "        while i < len(s):\n",
    "            length = int(s[i:i+4])\n",
    "            i += 4\n",
    "            strs.append(s[i:i+length])\n",
    "            i += length\n",
    "        return strs\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "    def encode(self, strs: List[str]):\n",
    "        if not strs:\n",
    "            return chr(258)\n",
    "        return chr(259).join(strs)\n",
    "        \n",
    "    def decode(self, s):\n",
    "        if s == chr(258):\n",
    "            return []\n",
    "        return s.split(chr(259))\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '|'.join([s.replace('|', '\\\\|') for s in strs])\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        tmp = \"\"\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            c = s[i]\n",
    "            if c == '|':\n",
    "                ret.append(tmp)\n",
    "                tmp = \"\"\n",
    "                i += 1\n",
    "            elif c == '\\\\' and i + 1 < len(s) and s[i + 1] == '|':\n",
    "                tmp += '|'\n",
    "                i += 2\n",
    "            else:\n",
    "                tmp += c\n",
    "                i += 1\n",
    "        ret.append(tmp)\n",
    "        return ret\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return ''.join(map(lambda s: f'{len(s)}#{s}', strs))\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while s[j] != '#':\n",
    "                j += 1\n",
    "            length = int(s[i:j])\n",
    "            i = j + 1\n",
    "            j = i + length\n",
    "            res.append(s[i:j])\n",
    "            i = j\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        list_ = []\n",
    "        for i in strs:\n",
    "            for j in i:\n",
    "                list_.append(j)\n",
    "            list_.append(\"\\n\")\n",
    "        return \"\".join(list_)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        str_ = \"\"\n",
    "        for i in s:\n",
    "            if i == \"\\n\":\n",
    "                ans.append(str_)\n",
    "                str_ = \"\"\n",
    "            else:\n",
    "                str_ += i\n",
    "        return ans\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = ''\n",
    "        num = 0\n",
    "        for c in strs:\n",
    "            num = len(c)\n",
    "            res += str(num) + '#' + c\n",
    "        # print(res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        words = []\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while s[j] != '#':\n",
    "                j += 1\n",
    "            num = int(s[i: j])\n",
    "            j += 1\n",
    "            word = s[j: j+num]\n",
    "            words.append(word)\n",
    "            j += num\n",
    "            i = j\n",
    "        return words\n",
    "\n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '%00%'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return s.split('%00%')\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = \"\"\n",
    "        for s in strs:\n",
    "            res += str(len(s))+\"#\"+s\n",
    "        return res\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        res, i = [], 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while s[j]!=\"#\":\n",
    "                j+=1\n",
    "            length = int(s[i:j])\n",
    "            res.append(s[j+1:j+1+length])\n",
    "            i = j+1+length\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return (chr(257)).join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        splitword = s.split(chr(257))\n",
    "        for w in splitword:\n",
    "            result.append(w)\n",
    "        return result\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return chr(258)\n",
    "        \n",
    "        return chr(257).join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        if s == chr(258): return []\n",
    "        return s.split(chr(257))\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        out = ''\n",
    "        for str_ in strs:\n",
    "            out += f'{len(str_):03}{str_}'\n",
    "        return out\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        pin = 0\n",
    "        s_len = len(s)\n",
    "        out = []\n",
    "        while pin < s_len:\n",
    "            word_len = int(s[pin:pin+3])\n",
    "            pin += 3\n",
    "            out.append(s[pin:pin+word_len])\n",
    "            pin += word_len\n",
    "        return out\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    # Use 4 bytes as header to indicate the length of string.\n",
    "    # Time O(n) Space O(n)\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        for s in strs:\n",
    "            length = str(len(s))\n",
    "            header = \"0\" * (4 - len(length)) + length\n",
    "            res.append(header)\n",
    "            res.append(s)\n",
    "        return \"\".join(res)\n",
    "\n",
    "    # Read first 4 bytes to get length. Then read length bytes for content.\n",
    "    # Time O(n) Space O(1)\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        read = 0\n",
    "        res = []\n",
    "        while read < n:\n",
    "            header = s[read:read+4]\n",
    "            read += 4\n",
    "            res.append(s[read:read+int(header)])\n",
    "            read += int(header)\n",
    "        return res\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        for char in strs:\n",
    "            if not char:\n",
    "                res.append('\\n')\n",
    "            else:\n",
    "                res.append(char)\n",
    "        return '\\t'.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        strs = s.split('\\t')\n",
    "        res = []\n",
    "        for char in strs:\n",
    "            if char == '\\n':\n",
    "                res.append('')\n",
    "            else:\n",
    "                res.append(char)\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        return '||'.join([s.replace('|', '%|%') for s in strs])\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        return [s.replace('%|%', '|') for s in s.split('||')]\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        s = '(break)'.join(strs)\n",
    "        return s\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        rs = s.split('(break)')\n",
    "        return rs\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        self.index = [0]\n",
    "        for s in strs:\n",
    "            self.index.append(len(s)+self.index[-1])\n",
    "        self.index.pop(0)\n",
    "        return ''.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        strs = []\n",
    "        for i in self.index:\n",
    "            strs.append(s[left:i])\n",
    "            left = i\n",
    "        return strs\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = ''\n",
    "        for s in strs:\n",
    "            res += str(len(s)) + '#' + s \n",
    "        return res \n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        i = 0 \n",
    "        res = []\n",
    "        while i < len(s):\n",
    "            j = i \n",
    "            while s[j] != '#':\n",
    "                j += 1\n",
    "            length = int(s[i:j])\n",
    "            res.append(s[j + 1: j + 1 + length])\n",
    "            i = j + 1 + length \n",
    "        return res \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        if len(strs) == 0: return ''\n",
    "        return ','.join([str(len(s)) for s in strs]) + '#' + ''.join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        if not s: return []\n",
    "        i = 0\n",
    "        while s[i] != '#': i += 1\n",
    "        lens = s[:i].split(',')\n",
    "        strs = s[i+1:]\n",
    "        res = []\n",
    "        i = 0\n",
    "        for l in lens:\n",
    "            l = int(l)\n",
    "            end = i + l\n",
    "            res.append(strs[i:end])\n",
    "            i = end\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        ret=''\n",
    "        for item in strs:\n",
    "            index1=item.find('/') if item.find('/')!=-1 else 0x7fffffff\n",
    "            index2=item.find('*') if item.find('*')!=-1 else 0x7fffffff\n",
    "            index=min(index1,index2)\n",
    "            temp=''\n",
    "            while index!=0x7fffffff:\n",
    "                item=item[:index]+'/'+item[index:]\n",
    "                temp+=item[:index+2]\n",
    "                item=item[index+2:]\n",
    "                index1=item.find('/') if item.find('/')!=-1 else 0x7fffffff\n",
    "                index2=item.find('*') if item.find('*')!=-1 else 0x7fffffff\n",
    "                index=min(index1,index2)\n",
    "            ret=ret+temp+item+'*'\n",
    "        return ret\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        ret=[]\n",
    "        while i<len(s):\n",
    "            if i==len(s)-1:\n",
    "                ret.append(s[:len(s)-1])\n",
    "                break\n",
    "            if s[i]=='/':\n",
    "                s=s[:i]+s[i+1:]\n",
    "                i+=1\n",
    "            elif s[i]=='*':\n",
    "                ret.append(s[:i])\n",
    "                s=s[i+1:]\n",
    "                i=0\n",
    "            else:\n",
    "                i+=1\n",
    "        return ret\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        for s in strs:\n",
    "            l = len(s)\n",
    "            ret.append(f\"{l}#{s}\")\n",
    "        return \"\".join(ret)\n",
    "        \n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        i = 0\n",
    "        #print(s)\n",
    "        while i < len(s):\n",
    "            cnt = 0\n",
    "            while i < len(s) and s[i].isdigit():\n",
    "                cnt = cnt * 10 + int(s[i])\n",
    "                i += 1\n",
    "            j = i + 1 + cnt\n",
    "            ret.append(s[i + 1: j])\n",
    "            i = j\n",
    "        return ret\n",
    "            \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "\n",
    "        \"\"\"\n",
    "        \n",
    "        ret = ''\n",
    "        for word in strs:\n",
    "            ret += (str(len(word)) + '#' + word)\n",
    "        return ret\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        \n",
    "        ret = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            l = i\n",
    "            while s[i]!= \"#\":\n",
    "                i += 1\n",
    "            length = int(s[l:i])\n",
    "            ret.append(s[i + 1: i + 1 + length])\n",
    "            i = i + 1 + length\n",
    "        return ret\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def int_to_char(self, s):\n",
    "        ans = format(s, 'x')\n",
    "        while len(ans) < 4:\n",
    "            ans = '0' + ans\n",
    "        return ans\n",
    "    \n",
    "    def char_to_int(self, ch):\n",
    "        i = 0\n",
    "        while i < 4 and ch[i] == '0':\n",
    "            i += 1\n",
    "        if i == 4:\n",
    "            return 0\n",
    "        return int(ch[i:], base=16)\n",
    "\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        ans = ''\n",
    "        for s in strs:\n",
    "            l = len(s)\n",
    "            ans += self.int_to_char(l)\n",
    "            ans += s\n",
    "        return ans\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            pre = s[i:i+4]\n",
    "            l = self.char_to_int(pre)\n",
    "            sstr = s[i+4: i+4+l]\n",
    "            ans.append(sstr)\n",
    "            i = i+4+l\n",
    "        return ans\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        ans1 = str(len(strs)) + '+*/@'\n",
    "        ans2 = ''\n",
    "        for s in strs:\n",
    "            ans1 += str(len(ans2)) + '+*/@'\n",
    "            ans2 += s\n",
    "\n",
    "        ans1 += str(len(ans2)) + '+*/@'\n",
    "\n",
    "        # print(ans1 + ans2)\n",
    "        return ans1 + ans2\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        s_list = s.split('+*/@')\n",
    "        len_s_list = len(s_list)\n",
    "\n",
    "        n = int(s_list[0])\n",
    "        id_list = []\n",
    "        for i in range(n+1):\n",
    "            id_list.append(int(s_list[i + 1]))\n",
    "        \n",
    "        if n + 3 == len_s_list:\n",
    "            ss = s_list[-1]\n",
    "        else:\n",
    "            ss = '+*/'.join(s[n + 2:])\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(id_list)-1):\n",
    "            ans.append(ss[id_list[i]: id_list[i + 1]])\n",
    "        \n",
    "        # print(i)\n",
    "        # if i != 0:\n",
    "        #     ans.append(ss[id_list[i+1]:]) \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.index_map = {}\n",
    "\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        if len(strs) == 1:\n",
    "            return strs[0]\n",
    "        encoded_str = \"\"\n",
    "        idx = 0\n",
    "        for i in range(len(strs)):\n",
    "            self.index_map[idx+len(strs[i])-1] = self.index_map.get(idx+len(strs[i])-1, 0) + 1\n",
    "            idx += len(strs[i])\n",
    "            encoded_str += strs[i]\n",
    "        print(encoded_str)\n",
    "        print(self.index_map)\n",
    "        return encoded_str\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        if not self.index_map:\n",
    "            return [s]\n",
    "        start = 0\n",
    "        res = []\n",
    "        for end in range(-1, len(s)):\n",
    "            if end in self.index_map:\n",
    "                res.append(s[start:end+1])\n",
    "                self.index_map[end] -= 1\n",
    "                while self.index_map[end]:\n",
    "                    res.append(\"\")\n",
    "                    self.index_map[end] -= 1\n",
    "                start = end + 1\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        out = ''\n",
    "        for str_ in strs:\n",
    "            head = f'{len(str_)}/'\n",
    "            end = '/'\n",
    "            out += f'{head}{str_}{end}'\n",
    "        return out\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        split_s = s.split('/')[:-1]\n",
    "        out = []\n",
    "        cur_s = ''\n",
    "        next_len = -1\n",
    "        while split_s:\n",
    "            cur_s += split_s.pop(0)\n",
    "            if next_len < 0:\n",
    "                next_len = int(cur_s)\n",
    "                cur_s = ''\n",
    "                continue\n",
    "            if len(cur_s) != next_len:\n",
    "                \"\"\"\n",
    "                string might contain '/'\n",
    "                \"\"\"\n",
    "                cur_s += '/'\n",
    "                continue\n",
    "            else:\n",
    "                out.append(cur_s)\n",
    "                cur_s = ''\n",
    "                next_len = -1\n",
    "        return out\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        out = ''\n",
    "        for str_ in strs:\n",
    "            head = f'{len(str_):03}'\n",
    "            out += f'{head}{str_}'\n",
    "        return out\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        pin = 0\n",
    "        s_len = len(s)\n",
    "        out = []\n",
    "        while pin < s_len:\n",
    "            word_len = int(s[pin:pin+3])\n",
    "            pin += 3\n",
    "            out.append(s[pin:pin+word_len])\n",
    "            pin += word_len\n",
    "        return out\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        n = len(strs)\n",
    "        \"\"\"\n",
    "        Head shoule be n,\n",
    "        \"\"\"\n",
    "        str_lens = [str(len(s)) for s in strs]\n",
    "\n",
    "        return f\"{n},\"+\",\".join(str_lens)+\",\"+\"\".join(strs)\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        n = int(s.split(',')[0])\n",
    "        str_lens = s.split(',')[1: n+1]\n",
    "        head_len = len(str(n)) + sum([len(l) for l in str_lens]) + len(str_lens) + 1\n",
    "        strs = []\n",
    "        accum = 0\n",
    "        content = s[head_len:]\n",
    "        for l in str_lens:\n",
    "            l = int(l)\n",
    "            sub_s = content[accum: accum + l]\n",
    "            accum += l\n",
    "            strs.append(sub_s)\n",
    "        return strs\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        list_ = []\n",
    "        for i in strs:\n",
    "            for j in i:\n",
    "                list_.append(j)\n",
    "            list_.append(\"\\n\")\n",
    "        return \"\".join(list_)\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        str_ = \"\"\n",
    "        print(s)\n",
    "        for i in s:\n",
    "            if i == \"\\n\":\n",
    "                ans.append(str_)\n",
    "                str_ = \"\"\n",
    "            else:\n",
    "                str_ += i\n",
    "        return ans\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = ''\n",
    "        num = 0\n",
    "        for c in strs:\n",
    "            num = len(c)\n",
    "            res += str(num) + '#' + c\n",
    "        # print(res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        idx = 0\n",
    "        n = len(s)\n",
    "        words = []\n",
    "        while idx < n:\n",
    "            if s[idx].isdigit():\n",
    "                start = idx\n",
    "                idx += 1\n",
    "                while s[idx].isdigit():\n",
    "                    idx += 1\n",
    "                num = int(s[start:idx])\n",
    "                idx += 1\n",
    "                word = s[idx:idx+num]\n",
    "                words.append(word)\n",
    "                idx += num\n",
    "\n",
    "        # print(words)\n",
    "        return words\n",
    "\n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: list[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        List = []\n",
    "        for i in strs:\n",
    "            for j in i:\n",
    "                if j == ' ':\n",
    "                    List.append('\\t')\n",
    "                else:\n",
    "                    List.append(j)\n",
    "            List.append('\\n')\n",
    "        List = ''.join(List)\n",
    "        return List\n",
    "\n",
    "    def decode(self, s: str) -> list[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        List = []\n",
    "        Str = ''\n",
    "        for i in s:\n",
    "            if i == '\\t':\n",
    "                Str = ''.join([Str, ' '])\n",
    "            else:\n",
    "                if i != '\\n':\n",
    "                    Str = ''.join([Str, i])\n",
    "                else:\n",
    "                    List.append(Str)\n",
    "                    Str = ''\n",
    "        return List\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = ''\n",
    "        num = 0\n",
    "        for c in strs:\n",
    "            num = len(c)\n",
    "            res += str(num) + '#' + c\n",
    "        # print(res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "\n",
    "        idx = 0\n",
    "        n = len(s)\n",
    "        words = []\n",
    "        while idx < n:\n",
    "            if s[idx].isdigit():\n",
    "                start = idx\n",
    "                idx += 1\n",
    "                while s[idx].isdigit():\n",
    "                    idx += 1\n",
    "                num = int(s[start: idx])\n",
    "                idx += 1\n",
    "                word = s[idx: idx+num]\n",
    "                words.append(word)\n",
    "                idx += num\n",
    "        return words\n",
    "\n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = \"\"\n",
    "        for strin in strs:\n",
    "            res += f\"{len(strin)}#{strin}\"\n",
    "        return res\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        i = 0\n",
    "        \n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while s[j] != '#':\n",
    "                j += 1\n",
    "            length = int(s[i:j])\n",
    "            i = j + 1\n",
    "            j = i + length\n",
    "            res.append(s[i:j])\n",
    "            i = j\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        send = \"\"\n",
    "        for s in strs:\n",
    "            send = send + str(len(s)) + \"@\" + s\n",
    "        return send\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        received = []\n",
    "        while s:\n",
    "            length = int(s.split(\"@\")[0])\n",
    "            start_idx = s.index(\"@\")\n",
    "            received.append(s[start_idx+1:start_idx+1+length])\n",
    "            s = s[start_idx+1+length:]\n",
    "        return received\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        # 例子：[\"leet\",\"code\"]\n",
    "        # \"4#leet4#code\"\n",
    "        # int: 0 #:1 str_len = int(s[0:1])=4 str1 = s[2:2+4]\n",
    "        res = \"\"\n",
    "        for s in strs:\n",
    "            res += str(len(s)) + \"#\" + s\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            # 找到第一个分隔符的索引位置\n",
    "            while s[j] != \"#\":\n",
    "                j += 1\n",
    "            \n",
    "            length = int(s[i:j])\n",
    "            ans.append(s[j+1:j+1+length])\n",
    "\n",
    "            i = j+length+1\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs: List[str]) -> str:\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        \"\"\"\n",
    "        res = \"\"\n",
    "        for s in strs:\n",
    "            res += str(len(s))+\"#\"+s\n",
    "        return res\n",
    "\n",
    "    def decode(self, s: str) -> List[str]:\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while s[j] != \"#\":\n",
    "                j += 1\n",
    "            length = int(s[i:j])\n",
    "            cur_str = s[j+1:j+1+length]\n",
    "            res.append(cur_str)\n",
    "            i = j+length+1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "        self.index = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        shortUrl = \"http://tingwei.com/\" + str(self.index)\n",
    "        self.map[shortUrl] = longUrl\n",
    "        self.index += 1\n",
    "        return shortUrl\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.map.get(shortUrl, None)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.dict1 = dict()\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.dict1[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(self.id)\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        i = shortUrl.rfind(\"/\")\n",
    "        id = int(shortUrl[i+1:])\n",
    "        return self.dict1[id]\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        s = \"\"\n",
    "        for i in longUrl:\n",
    "            s+=i\n",
    "            s+='1'\n",
    "        return s\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        s = ''\n",
    "        for i in range(len(shortUrl)):\n",
    "            if i%2==0:\n",
    "                s+=shortUrl[i]\n",
    "        return s\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(self.id)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        i = shortUrl.rfind('/')\n",
    "        id = int(shortUrl[i + 1:])\n",
    "        return self.database[id]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database = {0:0}\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        num3 = 0\n",
    "        while num3 in self.database:\n",
    "            num1 = random.randint(0,100000000)\n",
    "            num2 = random.randint(0,100000000)\n",
    "            num3 = num1^num2\n",
    "        else:\n",
    "            self.database[num3] = longUrl\n",
    "            return num3\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.database[shortUrl]        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    #关键在于唯一性即可\n",
    "    def __init__(self):\n",
    "        self.dict = {}\n",
    "        self.idx = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.idx +=1\n",
    "        self.dict[self.idx] = longUrl\n",
    "        str1 = longUrl.split(\"/\")[0]\n",
    "        return str1+\"/\"+str(self.idx)\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        #\n",
    "        idx = int(shortUrl.split(\"/\")[-1])\n",
    "        return self.dict[idx]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.d = dict()\n",
    "        self.idx = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.idx += 1\n",
    "        self.d[str(self.idx)] = longUrl\n",
    "        return str(self.idx)    \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.d[shortUrl]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.id = 0\n",
    "        self.database: Dict[str, str] = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\"\"\"\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(self.id)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\"\"\"\n",
    "        i = shortUrl.rfind('/')\n",
    "        id_ = int(shortUrl[i + 1:])\n",
    "        return self.database[id_]\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(self.id)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        i = shortUrl.rfind('/')\n",
    "        id = int(shortUrl[i + 1:])\n",
    "        return self.database[id]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.dataBase = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        out_str = sum([ord(i) for i in longUrl])\n",
    "        self.dataBase[out_str] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(out_str)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        i = shortUrl.rfind('/')\n",
    "        key = int(shortUrl[i + 1:])\n",
    "        return self.dataBase[key]\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\tdef __init__(self):\n",
    "\t\tself.a = []\n",
    "\n",
    "\tdef encode(self, longUrl: str) -> str:\n",
    "\t\tindex = len(self.a)\n",
    "\t\tself.a.append(longUrl)\n",
    "\t\treturn f'http://tinyurl.com/{index}'\n",
    "\n",
    "\tdef decode(self, shortUrl: str) -> str:\n",
    "\t\tindex = int(shortUrl[shortUrl.index('/', shortUrl.index('//') + 2) + 1:])\n",
    "\t\treturn self.a[index]   \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import random\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.origin_to_tiny = {}\n",
    "        self.tiny_to_origin = {}\n",
    "        self.k = 6\n",
    "        # self.prefix = 'https://acoier.com/tags/'\n",
    "        self.ss = string.ascii_letters + string.digits\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        while longUrl not in self.origin_to_tiny.keys():\n",
    "            cur = ''.join([self.ss[random.randint(0, len(self.ss) -1)] for _ in range(self.k)])\n",
    "            if cur in self.tiny_to_origin.keys():\n",
    "                continue\n",
    "            self.tiny_to_origin[cur] = longUrl\n",
    "            self.origin_to_tiny[longUrl] = cur\n",
    "        return self.origin_to_tiny[longUrl]        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.tiny_to_origin[shortUrl]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.encodedict=dict()\n",
    "        self.decodedict=dict()\n",
    "        self.id=0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.encodedict[longUrl]=self.id\n",
    "        self.decodedict[self.id]=longUrl\n",
    "        self.id+=1\n",
    "        return self.id-1\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.decodedict[shortUrl]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "        self.index = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        shortUrl = \"http://tinyurl.com/\" + str(self.index)\n",
    "        self.map[shortUrl] = longUrl\n",
    "        self.index += 1\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.map.get(shortUrl, None)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    " \n",
    "        return longUrl[::-1]\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "\n",
    "        return shortUrl[::-1]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.component = 'abcdefghijklmnopqrstuvwxyz' + '0123456789'\n",
    "        self.long2short = dict()\n",
    "        self.short2long = dict()\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        from random import randint\n",
    "        while True:\n",
    "            short = ''.join([self.component[randint(0, len(self.component) - 1)] for _ in range(6)])\n",
    "            if short not in self.short2long: break\n",
    "        self.short2long[short] = longUrl\n",
    "        self.long2short[longUrl] = short\n",
    "        return short\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.short2long[shortUrl]\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl/\" + str(self.id)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        i = shortUrl.rfind(\"/\")\n",
    "        id = int(shortUrl[i+1:])\n",
    "        return self.database[id]\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.encode_map = {}\n",
    "        self.decode_map = {}\n",
    "        self.counter = 0\n",
    "        self.base = 'https://tinyurl.com/'\n",
    "\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in self.encode_map:\n",
    "            return self.encode_map[longUrl]\n",
    "        \n",
    "        shortUrl = self.base + str(self.counter)\n",
    "        self.encode_map[longUrl] = shortUrl\n",
    "        self.decode_map[shortUrl] = longUrl\n",
    "        self.counter += 1\n",
    "\n",
    "        return shortUrl    \n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.decode_map.get(shortUrl, None)\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.m = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.m[longUrl]=longUrl\n",
    "        return longUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.m[shortUrl]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\r\n",
    "\r\n",
    "    def encode(self, longUrl: str) -> str:\r\n",
    "        \"\"\"Encodes a URL to a shortened URL.\r\n",
    "        \"\"\"\r\n",
    "        return longUrl + 'x'\r\n",
    "        \r\n",
    "\r\n",
    "    def decode(self, shortUrl: str) -> str:\r\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\r\n",
    "        \"\"\"\r\n",
    "        return shortUrl[0:-1]\r\n",
    "        \r\n",
    "\r\n",
    "# Your Codec object will be instantiated and called as such:\r\n",
    "# codec = Codec()\r\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.origin_to_tiny = {}\n",
    "        self.tiny_to_origin = {}\n",
    "        self.k = 6\n",
    "        self.prefix = 'https://acoier.com/tags/'\n",
    "        self.ss = string.ascii_letters + string.digits\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        while longUrl not in self.origin_to_tiny.keys():\n",
    "            cur = ''.join([self.ss[random.randint(0,len(self.ss) - 1)] for _ in range(self.k)])\n",
    "            if cur in self.tiny_to_origin.keys():\n",
    "                continue\n",
    "            self.tiny_to_origin[cur] = longUrl\n",
    "            self.origin_to_tiny[longUrl] = cur\n",
    "        return self.origin_to_tiny[longUrl]\n",
    "        \n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        return self.tiny_to_origin[shortUrl]\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.en = {}\n",
    "        self.de = {}\n",
    "        self.base = 'http://tinyurl.com/'\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl not in self.en:\n",
    "            shortUrl = self.base + str(len(self.en) + 1)\n",
    "            self.en[longUrl] = shortUrl\n",
    "            self.de[shortUrl] = longUrl\n",
    "        return shortUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.de[shortUrl]\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        shortUrl = \"http://tinyurl.com/\" + str(self.id)\n",
    "        self.map[shortUrl] = longUrl\n",
    "        self.id += 1\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.map.get(shortUrl, None)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\r\n",
    "\r\n",
    "    def encode(self, longUrl: str) -> str:\r\n",
    "        \"\"\"Encodes a URL to a shortened URL.\r\n",
    "        \"\"\"\r\n",
    "        return longUrl\r\n",
    "        \r\n",
    "\r\n",
    "    def decode(self, shortUrl: str) -> str:\r\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\r\n",
    "        \"\"\"\r\n",
    "        return shortUrl\r\n",
    "        \r\n",
    "\r\n",
    "# Your Codec object will be instantiated and called as such:\r\n",
    "# codec = Codec()\r\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    " \n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.dataBase = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        out_str = sum([ord(i) for i in longUrl])\n",
    "        self.dataBase[out_str] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(out_str)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        i = shortUrl.rfind('/')\n",
    "        key = int(shortUrl[i + 1:])\n",
    "        return self.dataBase[key]\n",
    "# class Codec:\n",
    "#     def __init__(self):\n",
    "#         self.dataBase = {}\n",
    "\n",
    "#     def encode(self, longUrl: str) -> str:\n",
    "#         out_str = int(str(hash(longUrl))[-10:])\n",
    "#         # out_str = sum([ord(i) for i in longUrl])\n",
    "#         self.dataBase[out_str] = longUrl\n",
    "#         return \"http://tinyurl.com/\" + str(out_str)\n",
    "\n",
    "#     def decode(self, shortUrl: str) -> str:\n",
    "#         i = shortUrl.rfind('/')\n",
    "#         key = int(shortUrl[i + 1:])\n",
    "#         return self.dataBase[key]\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.data = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.data[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\"+str(self.id)\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        id_str = shortUrl.split(\"/\")[-1]\n",
    "        return self.data[int(id_str)]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl.com\" + str(self.id)\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        id = int(shortUrl[18:])\n",
    "        return self.database[id]\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(self.id)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        i = shortUrl.rfind('/')\n",
    "        id = int(shortUrl[i + 1:])\n",
    "        return self.database[id]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.l2s = {}\n",
    "        self.s2l = {}\n",
    "        self.chars = [str(i) for i in range(10)] + [chr(ord(\"a\") + i) for i in range(26)] + [chr(ord(\"A\") + i) for i in range(26)]\n",
    "        self.prefix = \"https://tinyurl/\"\n",
    "\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in self.l2s:\n",
    "            return self.l2s[longUrl]\n",
    "        \n",
    "        randomval = self.chars[random.randrange(0, len(self.chars))]\n",
    "        while randomval in self.s2l:\n",
    "            randomval+=self.chars[random.randrange(0, len(self.chars))]\n",
    "        self.s2l[randomval] = longUrl\n",
    "        self.l2s[longUrl] = self.prefix + randomval \n",
    "\n",
    "        return self.l2s[longUrl]\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.s2l[shortUrl.split(\"/\")[-1]]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.data = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.data[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\"+str(self.id)\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        a = shortUrl.rfind('/')\n",
    "        id = int(shortUrl[a+1:])\n",
    "        return self.data[id]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        #http_groups = longUrl.split(\"//\")\n",
    "\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "\n",
    "        #http_groups = shortUrl.split(\"//\")\n",
    "\n",
    "        return shortUrl #http_groups[0] + \"//\" +http_groups[1][::-1]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database={}\n",
    "        self.id = 0\n",
    "\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\"+str(self.id)\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        index = shortUrl.rfind('/')\n",
    "        return self.database[int(shortUrl[index+1:])]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import random\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.key_to_val = {}\n",
    "        self.val_to_key = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        k = 1 + len(longUrl) // 2\n",
    "        newkey = \"\".join(random.choices(string.ascii_letters, k = k))\n",
    "        while newkey in self.key_to_val:\n",
    "            newkey = \"\".join(random.choices(string.ascii_letters, k = k))\n",
    "        self.key_to_val[newkey] = longUrl\n",
    "        self.val_to_key[longUrl] = newkey\n",
    "        return newkey\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.key_to_val[shortUrl] \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl+'a'\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl[:-1]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "k1,k2=1117,10**9+7\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.urlToKey={}\n",
    "        self.dataBase={}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in self.urlToKey:\n",
    "            return \"http://tinyurl.com/\" + str(urlToKey(longUrl))\n",
    "        key,base=0,1\n",
    "        for c in longUrl:\n",
    "            key=(key+ord(c)*base)%k2\n",
    "            base=(base*k1)%k2\n",
    "        while key in self.dataBase:\n",
    "            key=(key+1)%2\n",
    "        self.dataBase[key]=longUrl\n",
    "        self.urlToKey[longUrl]=key\n",
    "        return \"http://tinyurl.com/\" + str(key)\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        i=shortUrl.rfind(\"/\")\n",
    "        key=int(shortUrl[i+1:])\n",
    "        return self.dataBase[key]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import random\n",
    "import math\n",
    "fully_tiny = {}\n",
    "tiny_full = {}\n",
    "letters = string.ascii_letters + string.digits\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        def short_addr():\n",
    "            ans = ''\n",
    "            temp = ''\n",
    "            for i in range(6):\n",
    "                temp = letters[random.randint(1, 1000) % 62]\n",
    "                ans += temp\n",
    "            return ans\n",
    "\n",
    "        if longUrl in fully_tiny:\n",
    "            return 'http://tinyurl.com/' + fully_tiny[longUrl]\n",
    "        else:\n",
    "            suffix = short_addr()\n",
    "            fully_tiny[longUrl] = suffix\n",
    "            tiny_full[suffix] = longUrl\n",
    "            return 'http://tinyurl.com/' + suffix\n",
    "        \n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        shortUrl = shortUrl.split('/')[-1]\n",
    "        if shortUrl in tiny_full:\n",
    "            return tiny_full[shortUrl]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.hash_map = {}\n",
    "        self.id = 0\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.hash_map[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(self.id)\n",
    "\n",
    "        \n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.hash_map[int(shortUrl.split('/')[-1])]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.db = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        hashed = hash(longUrl) % 2000\n",
    "        self.db[hashed] = longUrl\n",
    "        return hashed\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.db[shortUrl]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import math\n",
    "import random\n",
    "letters = string.ascii_letters + string.digits\n",
    "fully_tiny = {}\n",
    "tiny_fully = {}\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        def short_addr():\n",
    "            temp = ''\n",
    "            ans = ''\n",
    "            for i in range(6):\n",
    "                temp = letters[random.randint(0, 10000) % 62]\n",
    "                ans += temp\n",
    "            return ans\n",
    "        if longUrl in fully_tiny:\n",
    "            return 'http://tinyurl.com/' + fully_tiny[longUrl]\n",
    "        else:\n",
    "            suffix = short_addr()\n",
    "            fully_tiny[longUrl] = suffix\n",
    "            tiny_fully[suffix] = longUrl\n",
    "            return 'http://tinyurl.com/' + suffix\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        shortUrl = shortUrl.split('/')[-1]\n",
    "        if shortUrl in tiny_fully:\n",
    "            return tiny_fully[shortUrl]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.database = {}\n",
    "        self.id = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        self.id += 1\n",
    "        self.database[self.id] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(self.id)\n",
    "\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        i = shortUrl.rfind('/')\n",
    "        id = int(shortUrl[i+1:])\n",
    "        return self.database[id]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    index = 0\n",
    "    long2Short = {}\n",
    "    short2Long = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        if longUrl in self.long2Short:\n",
    "            return str(self.long2Short[longUrl])\n",
    "\n",
    "        self.long2Short[longUrl] = self.index\n",
    "        self.short2Long[self.index] = longUrl\n",
    "        self.index += 1\n",
    "        return str(self.index - 1)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        return self.short2Long.get(int(shortUrl), '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.db = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        hashed = hash(longUrl) % 1000\n",
    "        self.db[hashed] = longUrl\n",
    "        return hashed\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.db[shortUrl]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Codec:\n",
    "#     def __init__(self):\n",
    "#         self.dataBase = {}\n",
    "\n",
    "#     def encode(self, longUrl: str) -> str:\n",
    "#         \"\"\"Encodes a URL to a shortened URL.\n",
    "#         \"\"\"\n",
    "#         out_str = sum([ord(i) for i in longUrl])\n",
    "#         self.dataBase[out_str] = longUrl\n",
    "#         return \"http://tinyurl.com/\" + str(out_str)\n",
    "\n",
    "#     def decode(self, shortUrl: str) -> str:\n",
    "#         \"\"\"Decodes a shortened URL to its original URL.\n",
    "#         \"\"\"\n",
    "#         i = shortUrl.rfind('/')\n",
    "#         key = int(shortUrl[i + 1:])\n",
    "#         return self.dataBase[key]\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.dataBase = {}\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        out_str = int(str(hash(longUrl))[-10:])\n",
    "        # out_str = sum([ord(i) for i in longUrl])\n",
    "        self.dataBase[out_str] = longUrl\n",
    "        return \"http://tinyurl.com/\" + str(out_str)\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        i = shortUrl.rfind('/')\n",
    "        key = int(shortUrl[i + 1:])\n",
    "        return self.dataBase[key]\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self) -> None:\n",
    "        self.encode_map = {}\n",
    "        self.decode_map = {}\n",
    "        self.counter = 0\n",
    "        self.base_url = \"http://tinyurl.com/\"\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in self.encode_map:\n",
    "            return self.encode_map[longUrl]\n",
    "        \n",
    "        shortUrl = self.base_url + str(self.counter)\n",
    "        self.encode_map[longUrl] = shortUrl\n",
    "        self.decode_map[shortUrl] = longUrl\n",
    "        self.counter += 1\n",
    "        \n",
    "        return shortUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.decode_map.get(shortUrl, None)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "        self.index = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        shortUrl = \"http.tingwei.com/\" + str(self.index)\n",
    "        self.map[shortUrl] = longUrl\n",
    "        self.index += 1\n",
    "        return shortUrl\n",
    "        \n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.map.get(shortUrl, None)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "        self.index = 0\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        shortUrl = \"http://tingwei.com/\" + str(self.index)\n",
    "        self.map[shortUrl] = longUrl\n",
    "        self.index += 1\n",
    "        return shortUrl\n",
    "        \n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.map.get(shortUrl, None)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        http_groups = longUrl.split(\"//\")\n",
    "\n",
    "        return http_groups[0] +\"//\"+ http_groups[1][::-1]\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "\n",
    "        http_groups = shortUrl.split(\"//\")\n",
    "\n",
    "        return http_groups[0] + \"//\" +http_groups[1][::-1]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self) -> None:\n",
    "        self.encode_map = {}\n",
    "        self.decode_map = {}\n",
    "        self.counter = 0\n",
    "        self.base_url = \"http://tinyurl.com/\"\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in self.encode_map:\n",
    "            return self.encode_map[longUrl]\n",
    "        \n",
    "        shortUrl = self.base_url + str(self.counter)\n",
    "        self.encode_map[longUrl] = shortUrl\n",
    "        self.decode_map[shortUrl] = longUrl\n",
    "        self.counter += 1\n",
    "        \n",
    "        return shortUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return self.decode_map.get(shortUrl, None)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        return longUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return shortUrl\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import random\n",
    "\n",
    "\n",
    "ascii_letters=string.digits+string.ascii_letters\n",
    "long2short={}\n",
    "short2long={}\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in long2short:\n",
    "            return 'http://tinyurl.com/'+long2short[longUrl]\n",
    "        short=''\n",
    "        for i in range(6):\n",
    "            short+=random.choice(ascii_letters)\n",
    "        long2short[longUrl]=short\n",
    "        short2long[short]=longUrl\n",
    "        return 'http://tinyurl.com/'+short\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        short=shortUrl.split('/')[-1]\n",
    "        if short in short2long:\n",
    "            return short2long[short]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import random\n",
    "import math\n",
    "fully_tiny = {}\n",
    "tiny_full = {}\n",
    "letters = string.ascii_letters + string.digits\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        def short_addr():\n",
    "            ans = ''\n",
    "            temp = ''\n",
    "            for i in range(6):\n",
    "                temp = letters[random.randint(1, 1000) % 62]\n",
    "                ans += temp\n",
    "            return ans\n",
    "\n",
    "        if longUrl in fully_tiny:\n",
    "            return 'http://tinyurl.com/' + fully_tiny[longUrl]\n",
    "        else:\n",
    "            suffix = short_addr()\n",
    "            fully_tiny[longUrl] = suffix\n",
    "            tiny_full[suffix] = longUrl\n",
    "            return 'http://tinyurl.com/' + suffix\n",
    "        \n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        shortUrl = shortUrl.split('/')[-1]\n",
    "        if shortUrl in tiny_full:\n",
    "            return tiny_full[shortUrl]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.url_id={}\r\n",
    "        self.id_url={}\r\n",
    "        self.idx=0\r\n",
    "    def encode(self, longUrl: str) -> str:\r\n",
    "        \"\"\"Encodes a URL to a shortened URL.\r\n",
    "        \"\"\"\r\n",
    "        if longUrl not in self.url_id:            \r\n",
    "            self.url_id[longUrl]=self.idx\r\n",
    "            self.id_url[self.idx]=longUrl\r\n",
    "            self.idx+=1\r\n",
    "        return 'http://tinyurl.com/'+str(self.url_id[longUrl])\r\n",
    "\r\n",
    "    def decode(self, shortUrl: str) -> str:\r\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\r\n",
    "        \"\"\"\r\n",
    "        idx=shortUrl.split('/')[-1]\r\n",
    "        return self.id_url[int(idx)]\r\n",
    "        \r\n",
    "\r\n",
    "# Your Codec object will be instantiated and called as such:\r\n",
    "# codec = Codec()\r\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import math\n",
    "import random\n",
    "letters = string.ascii_letters + string.digits\n",
    "fully_tiny = {}\n",
    "tiny_fully = {}\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        def short_addr():\n",
    "            temp = ''\n",
    "            ans = ''\n",
    "            for i in range(6):\n",
    "                temp = letters[random.randint(0, 10000) % 62]\n",
    "                ans += temp\n",
    "            return ans\n",
    "        if longUrl in fully_tiny:\n",
    "            return 'http://tinyurl.com/' + fully_tiny[longUrl]\n",
    "        else:\n",
    "            suffix = short_addr()\n",
    "            fully_tiny[longUrl] = suffix\n",
    "            tiny_fully[suffix] = longUrl\n",
    "            return 'http://tinyurl.com/' + suffix\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        shortUrl = shortUrl.split('/')[-1]\n",
    "        if shortUrl in tiny_fully:\n",
    "            return tiny_fully[shortUrl]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import random\n",
    "\n",
    "ascii_letters=string.digits+string.ascii_letters\n",
    "short2long={}\n",
    "long2short={}\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in long2short:\n",
    "            return 'http://tinyurl.com/'+long2short[longUrl]\n",
    "        shortUrl=''\n",
    "        for i in range(6):\n",
    "            shortUrl+=random.choice(ascii_letters)\n",
    "        long2short[longUrl]=shortUrl\n",
    "        short2long[shortUrl]=longUrl\n",
    "        return 'http://tinyurl.com/'+shortUrl\n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        short=shortUrl.split('/')[-1]\n",
    "        if short in short2long:\n",
    "            return short2long[short]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    l2s = {}\n",
    "    s2l = {}\n",
    "    chars = [str(i) for i in range(10)] + [chr(ord(\"a\") + i) for i in range(26)] + [chr(ord(\"A\") + i) for i in range(26)]\n",
    "    prefix = \"https://tinyurl/\"\n",
    "\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in Codec.l2s:\n",
    "            return Codec.l2s[longUrl]\n",
    "        \n",
    "        randomval = Codec.chars[random.randrange(0, len(Codec.chars))]\n",
    "        while randomval in Codec.s2l:\n",
    "            randomval+=Codec.chars[random.randrange(0, len(Codec.chars))]\n",
    "        Codec.s2l[randomval] = longUrl\n",
    "        Codec.l2s[longUrl] = Codec.prefix + randomval \n",
    "\n",
    "        return Codec.l2s[longUrl]\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        return Codec.s2l[shortUrl.split(\"/\")[-1]]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "import random\n",
    "\n",
    "ascii_letters=string.digits+string.ascii_letters\n",
    "long2short={}\n",
    "short2long={}\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "        \"\"\"\n",
    "        if longUrl in long2short:\n",
    "            return 'http://tinyurl.com/'+long2short[longUrl]\n",
    "        shortUrl=''\n",
    "        for i in range(6):\n",
    "            shortUrl+=random.choice(ascii_letters)\n",
    "        long2short[longUrl]=shortUrl\n",
    "        short2long[shortUrl]=longUrl\n",
    "        return 'http://tinyurl.com/'+shortUrl\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "        short=shortUrl.split('/')[-1]\n",
    "        if short in short2long:\n",
    "            return short2long[short]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(url))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        rootNode = TreeNode(root.val)\n",
    "        queue = deque([(rootNode, root)])\n",
    "        while queue:\n",
    "            parent, curr = queue.popleft()\n",
    "            prevBNode = None\n",
    "            headBNode = None\n",
    "            for child in curr.children:\n",
    "                newBNode = TreeNode(child.val)\n",
    "                if prevBNode:\n",
    "                    prevBNode.right = newBNode\n",
    "                else:\n",
    "                    headBNode = newBNode\n",
    "                prevBNode = newBNode\n",
    "                queue.append((newBNode, child))\n",
    "            parent.left = headBNode\n",
    "        return rootNode\n",
    "    \n",
    "    \n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "        rootNode = Node(data.val, [])\n",
    "        queue = deque([(rootNode, data)])\n",
    "        while queue:\n",
    "            parent, curr = queue.popleft()\n",
    "            firstChild = curr.left\n",
    "            sibling = firstChild\n",
    "            while sibling:\n",
    "                newNode = Node(sibling.val, [])\n",
    "                parent.children.append(newNode)\n",
    "                queue.append((newNode, sibling))\n",
    "                sibling = sibling.right\n",
    "        return rootNode\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root: return \n",
    "        node = TreeNode(root.val)\n",
    "        if root.children:\n",
    "            node.left = self.encode(root.children[0])\n",
    "            cur = node.left\n",
    "            for child in root.children[1:]:\n",
    "                cur.right = self.encode(child)\n",
    "                cur = cur.right\n",
    "        return node\n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data: return\n",
    "        root = Node(data.val, [])\n",
    "        if data.left:\n",
    "            root.children.append(self.decode(data.left))\n",
    "            cur = data.left\n",
    "            while cur.right:\n",
    "                root.children.append(self.decode(cur.right))\n",
    "                cur = cur.right\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return \n",
    "        ans = TreeNode(root.val)\n",
    "        if root.children:\n",
    "            ans.left = self.encode(root.children[0])\n",
    "            cur = ans.left\n",
    "            for child in root.children[1:]:\n",
    "                cur.right = self.encode(child)\n",
    "                cur = cur.right\n",
    "        return ans \n",
    "\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return \n",
    "        root = Node(data.val, [])\n",
    "        if data.left:\n",
    "            root.children.append(self.decode(data.left))\n",
    "            cur = data.left \n",
    "            while cur.right:\n",
    "                root.children.append(self.decode(cur.right))\n",
    "                cur = cur.right\n",
    "        return root        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "# ### 官1：BFS \n",
    "# class Codec:\n",
    "#     # Encodes an n-ary tree to a binary tree.\n",
    "#     def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "#         ###1.边界条件判断\n",
    "#         if not root: return None\n",
    "\n",
    "#         rootNode=TreeNode(root.val)\n",
    "#         q=deque([(rootNode,root)])\n",
    "\n",
    "#         while q:\n",
    "#             parent,curr=q.popleft()\n",
    "#             prev,head=None,None ###同父的孩子转换成右子结点（单链表）\n",
    "#             for child in curr.children:\n",
    "#                 new=TreeNode(child.val)\n",
    "#                 if prev:\n",
    "#                     prev.right=new  \n",
    "#                 else:\n",
    "#                     head=new  \n",
    "#                 prev=new \n",
    "#                 q.append((prev,child))\n",
    "#             ### 老树的父节点的左子结点为原孩子的第一个\n",
    "#             parent.left=head \n",
    "        \n",
    "#         return rootNode\n",
    "        \t\n",
    "# \t# Decodes your binary tree to an n-ary tree.\n",
    "#     def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "#         ## 1.边界条件\n",
    "#         if not data:return None \n",
    "#         ### 2.2叉树解码成N叉树\n",
    "#         rootNode=Node(data.val,[])\n",
    "\n",
    "#         q=deque([(rootNode,data)])\n",
    "\n",
    "#         while q:\n",
    "#             parent,curr=q.popleft()\n",
    "#             first=curr.left \n",
    "#             sub=first\n",
    "#             while sub:\n",
    "#                 new=Node(sub.val,[])\n",
    "#                 parent.children.append(new)\n",
    "#                 q.append((new,sub))\n",
    "#                 sub=sub.right \n",
    "        \n",
    "#         return rootNode\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))\n",
    "\n",
    "###官2：DFS\n",
    "class Codec:\n",
    "    def encode(self,root):\n",
    "        ### 1. 边界条件\n",
    "        if not root:\n",
    "            return None \n",
    "        ### 编码\n",
    "        rootNode=TreeNode(root.val)\n",
    "        if len(root.children)>0:\n",
    "            first=root.children[0]\n",
    "            rootNode.left=self.encode(first)\n",
    "        #其余孩子的父节点\n",
    "        curr=rootNode.left\n",
    "        ###剩余孩子编码\n",
    "        for i in range(1,len(root.children)):\n",
    "            curr.right=self.encode(root.children[i])\n",
    "            curr=curr.right \n",
    "\n",
    "        return rootNode\n",
    "\n",
    "    def decode(self,data): ###将二叉树解码为N叉树\n",
    "        #1.边界条件\n",
    "        if not data:return None\n",
    "\n",
    "        rootNode=Node(data.val,[])\n",
    "\n",
    "        cur=data.left \n",
    "        while cur:\n",
    "            rootNode.children.append(self.decode(cur))\n",
    "            cur=cur.right\n",
    "        \n",
    "        return rootNode\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        res=TreeNode(root.val)\n",
    "        if root.children:\n",
    "            res.left=self.encode(root.children[0])\n",
    "            cur=res.left\n",
    "            for child in root.children[1:]:\n",
    "                cur.right=self.encode(child)\n",
    "                cur=cur.right\n",
    "        return res\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return\n",
    "        root=Node(data.val,[])\n",
    "        if data.left:\n",
    "            root.children.append(self.decode(data.left))\n",
    "            cur=data.left\n",
    "            while cur.right:\n",
    "                root.children.append(self.decode(cur.right))\n",
    "                cur=cur.right\n",
    "        return root \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        res = TreeNode(root.val)\n",
    "        if root.children:\n",
    "            res.left = self.encode(root.children[0])\n",
    "            cur = res.left\n",
    "            for node in root.children[1:]:\n",
    "                cur.right = self.encode(node)\n",
    "                cur = cur.right\n",
    "        return res        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return\n",
    "        res = Node(data.val, [])\n",
    "        cur = data.left\n",
    "        while cur:\n",
    "            res.children.append(self.decode(cur))\n",
    "            cur = cur.right\n",
    "        return res\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        btRoot = TreeNode(root.val)\n",
    "        q = [(btRoot, root)]\n",
    "\n",
    "        while q:\n",
    "            btNode, ntNode = q.pop(0)\n",
    "            dummy = TreeNode()\n",
    "            p = dummy \n",
    "            \n",
    "            for child in ntNode.children:\n",
    "                newBtNode = TreeNode(child.val)\n",
    "                q.append((newBtNode, child))\n",
    "                p.right = newBtNode\n",
    "                p = p.right\n",
    "\n",
    "            btNode.left = dummy.right \n",
    "\n",
    "        return btRoot\n",
    "\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if data is None:\n",
    "            return None\n",
    "\n",
    "        ntRoot = Node(data.val)\n",
    "        q = [(ntRoot, data)]\n",
    "\n",
    "        while q:\n",
    "            ntNode, btNode = q.pop(0)\n",
    "\n",
    "            child = btNode.left\n",
    "            child_lst = []\n",
    "            while child:\n",
    "                newNtNode = Node(child.val)\n",
    "                child_lst.append(newNtNode)\n",
    "                q.append((newNtNode, child))\n",
    "                child = child.right \n",
    "            \n",
    "            ntNode.children = child_lst\n",
    "\n",
    "        return ntRoot\n",
    "            \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "        troot = TreeNode(root.val)\n",
    "        troot.left = self.toTreeNode(root.children)\n",
    "        return troot\n",
    "\n",
    "\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if data == None:\n",
    "            return None\n",
    "        root = Node(data.val)\n",
    "        root.children = self.toNode(data.left)\n",
    "        return root\n",
    "\n",
    "    \n",
    "    def toTreeNode(self, children):\n",
    "        if children == None:\n",
    "            return None\n",
    "        pre = TreeNode()\n",
    "        curr = pre\n",
    "        i, n = 0, len(children)\n",
    "        while i < n:\n",
    "            curr.right = TreeNode(children[i].val)\n",
    "            curr.right.left = self.toTreeNode(children[i].children)\n",
    "            curr = curr.right\n",
    "            i += 1\n",
    "        return pre.right\n",
    "        \n",
    "\n",
    "    def toNode(self, tnode):\n",
    "        children = []\n",
    "        if not tnode:\n",
    "            return []\n",
    "        while tnode:\n",
    "            node = Node(tnode.val)\n",
    "            node.children = self.toNode(tnode.left)\n",
    "            children.append(node)\n",
    "            tnode = tnode.right\n",
    "        return children\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        # 左节点 是儿子 右边的节点是这个儿子节点的兄弟节点\n",
    "        if root == None:\n",
    "            return None\n",
    "        res = TreeNode(root.val)\n",
    "        if root.children:\n",
    "            res.left = self.encode(root.children[0])\n",
    "            cur = res.left\n",
    "            for node in root.children[1:]:\n",
    "                cur.right = self.encode(node)\n",
    "                cur = cur.right\n",
    "        return res                \n",
    "\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return None\n",
    "        res = Node(data.val, [])\n",
    "        cur = data.left\n",
    "        while cur:\n",
    "            res.children.append(self.decode(cur))\n",
    "            cur = cur.right\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "class Codec:\n",
    "\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Node') -> TreeNode:\n",
    "        if not root: return\n",
    "        res = TreeNode(root.val)\n",
    "        if root.children:\n",
    "            res.left = self.encode(root.children[0])\n",
    "        cur = res.left\n",
    "        for node in root.children[1:]:\n",
    "            cur.right = self.encode(node)\n",
    "            cur = cur.right\n",
    "        return res\n",
    "\n",
    "    # Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: TreeNode) -> 'Node':\n",
    "        if not data: return\n",
    "        res = Node(data.val, [])\n",
    "        cur = data.left\n",
    "        while cur:\n",
    "            res.children.append(self.decode(cur))\n",
    "            cur = cur.right\n",
    "        return res\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        node = TreeNode(root.val)\n",
    "        if root.children:\n",
    "            node.left = self.encode(root.children[0])\n",
    "        t = node.left\n",
    "        for x in root.children[1:]:\n",
    "            t.right = self.encode(x)\n",
    "            t = t.right\n",
    "        return node\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return\n",
    "        root = Node(data.val,[])\n",
    "        t = data.left\n",
    "        while t:\n",
    "            root.children.append(self.decode(t))\n",
    "            t = t.right\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "        tnode = TreeNode(root.val)\n",
    "        pre = TreeNode()\n",
    "        curr = pre\n",
    "        i, n = 0, len(root.children)\n",
    "        while i < n:\n",
    "            curr.right = self.encode(root.children[i])\n",
    "            curr = curr.right\n",
    "            i += 1\n",
    "        tnode.left = pre.right\n",
    "        return tnode\n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if data == None:\n",
    "            return None\n",
    "        nnode = Node(data.val, [])\n",
    "        tnode = data.left\n",
    "        while tnode:\n",
    "            nnode.children.append(self.decode(tnode))\n",
    "            tnode = tnode.right\n",
    "        return nnode\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        parent = TreeNode(root.val)\n",
    "        if not root.children:\n",
    "            return parent\n",
    "        else:\n",
    "            big_bro = self.encode(root.children[0])\n",
    "            parent.left = big_bro\n",
    "\n",
    "            pt = big_bro\n",
    "            for node in root.children[1:]:\n",
    "                pt.right = self.encode(node)\n",
    "                pt = pt.right\n",
    "            return parent\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return None\n",
    "        parent = Node(data.val, [])\n",
    "        if not data.left and not data.right:\n",
    "            return parent\n",
    "        \n",
    "        if data.left:\n",
    "            parent.children.append(\n",
    "                self.decode(data.left)\n",
    "            )\n",
    "\n",
    "            pt = data.left\n",
    "            while pt.right:\n",
    "                parent.children.append(\n",
    "                    self.decode(pt.right)\n",
    "                )\n",
    "                pt = pt.right\n",
    "        return parent\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        parent = TreeNode(root.val)\n",
    "        if not root.children:\n",
    "            return parent\n",
    "        else:\n",
    "            big_bro = self.encode(root.children[0])\n",
    "            parent.left = big_bro\n",
    "\n",
    "            pt = big_bro\n",
    "            for node in root.children[1:]:\n",
    "                ot_bro = self.encode(node)\n",
    "                pt.right = ot_bro\n",
    "                pt = pt.right\n",
    "            return parent\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return None\n",
    "        parent = Node(data.val, [])\n",
    "        if not data.left and not data.right:\n",
    "            return parent\n",
    "        \n",
    "        if data.left:\n",
    "            parent.children.append(\n",
    "                self.decode(data.left)\n",
    "            )\n",
    "\n",
    "            pt = data.left\n",
    "            while pt.right:\n",
    "                parent.children.append(\n",
    "                    self.decode(pt.right)\n",
    "                )\n",
    "                pt = pt.right\n",
    "        return parent\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, root):\n",
    "        \"\"\"Encodes an n-ary tree to a binary tree.\n",
    "        \n",
    "        :type root: Node\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root is None: return None\n",
    "        res =  TreeNode(root.val)\n",
    "        if(len(root.children) != 0): \n",
    "            res.left = self.encode(root.children[0])\n",
    "        cur = res.left\n",
    "        for i in range(1, len(root.children)):\n",
    "            cur.right = self.encode(root.children[i])\n",
    "            cur = cur.right\n",
    "        return res\n",
    "\n",
    "    def decode(self, root):\n",
    "        \"\"\"Decodes your binary tree to an n-ary tree.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        if not root: return None\n",
    "        res = Node(root.val, [])\n",
    "        cur = root.left\n",
    "        while(cur):\n",
    "            res.children.append(self.decode(cur))\n",
    "            cur = cur.right\n",
    "        return res\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, root):\n",
    "        if not root:\n",
    "           return None\n",
    "        rootNode= TreeNode(root.val)\n",
    "        q = collections.deque([(rootNode,root)])\n",
    "        while q:\n",
    "            pa,cur = q.popleft()\n",
    "            pre,head = None,None\n",
    "            for child in cur.children:\n",
    "                newNode = TreeNode(child.val)\n",
    "                if pre:\n",
    "                    pre.right = newNode\n",
    "                else:\n",
    "                    head = newNode\n",
    "                pre = newNode\n",
    "                q.append((newNode,child))\n",
    "            pa.left = head\n",
    "        return rootNode\n",
    "\n",
    "\n",
    "    def decode(self, data):\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "       # 应将缺省值设置为[]，而不是无，\n",
    "       # 否则它不会通过测试用例。\n",
    "        rootNode = Node(data.val, [])\n",
    "\n",
    "        q = collections.deque([(rootNode,data)])\n",
    "        \n",
    "\n",
    "        while q:\n",
    "            pa,cur = q.popleft()\n",
    "            first = cur.left\n",
    "            sib = first\n",
    "            while sib:\n",
    "                newNode = Node(sib.val,[])\n",
    "                pa.children.append(newNode)\n",
    "                q.append((newNode,sib))\n",
    "                sib = sib.right\n",
    "        return rootNode\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children or []\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def encode(self, root: Node) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        tree_node = TreeNode(x=root.val)\n",
    "        if root.children:\n",
    "            tree_node.left = self.encode(root.children[0])\n",
    "            other_node = tree_node.left\n",
    "\n",
    "            for i in range(1, len(root.children)):\n",
    "                other_node.right = self.encode(root.children[i])\n",
    "                other_node = other_node.right\n",
    "        return tree_node\n",
    "\n",
    "    def decode(self, data: TreeNode) -> Node:\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "        node = Node(val=data.val)\n",
    "        node.children = []\n",
    "        if data.left is None:\n",
    "            return node\n",
    "\n",
    "        other_node = data.left\n",
    "\n",
    "        while other_node:\n",
    "            node.children.append(self.decode(other_node))\n",
    "            other_node = other_node.right\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        queue = deque()\n",
    "        tree_root = TreeNode(root.val)\n",
    "        queue.append((root, tree_root))\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            (node, tree_node) = queue.popleft()\n",
    "\n",
    "            if len(node.children) == 0:\n",
    "                continue\n",
    "\n",
    "            cnode = node.children[0]\n",
    "            ctree_node = TreeNode(cnode.val)\n",
    "            tree_node.left = ctree_node\n",
    "\n",
    "            queue.append((cnode, ctree_node))\n",
    "\n",
    "            for i in range(1, len(node.children)):\n",
    "                inode = node.children[i]\n",
    "                itree_node = TreeNode(inode.val)\n",
    "\n",
    "                ctree_node.right = itree_node\n",
    "                ctree_node = itree_node\n",
    "\n",
    "                queue.append((inode, itree_node))\n",
    "\n",
    "        return tree_root\n",
    "\n",
    "    # Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if data is None:\n",
    "            return None\n",
    "            \n",
    "        root = Node(data.val)\n",
    "        queue = deque()\n",
    "        queue.append((data, root))\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            tree_node, node = queue.popleft()\n",
    "            node.children = list()\n",
    "\n",
    "            if tree_node.left is None:\n",
    "                continue\n",
    "\n",
    "            ctree_node = tree_node.left\n",
    "\n",
    "            while ctree_node is not None:\n",
    "                cnode = Node(ctree_node.val)\n",
    "                node.children.append(cnode)\n",
    "\n",
    "                queue.append((ctree_node, cnode))\n",
    "\n",
    "                ctree_node = ctree_node.right\n",
    "\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "### 官1：BFS \n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        ###1.边界条件判断\n",
    "        if not root: return None\n",
    "\n",
    "        rootNode=TreeNode(root.val)\n",
    "        q=deque([(rootNode,root)])\n",
    "\n",
    "        while q:\n",
    "            parent,curr=q.popleft()\n",
    "            prev,head=None,None ###同父的孩子转换成右子结点（单链表）\n",
    "            for child in curr.children:\n",
    "                new=TreeNode(child.val)\n",
    "                if prev:\n",
    "                    prev.right=new  \n",
    "                else:\n",
    "                    head=new  \n",
    "                prev=new \n",
    "                q.append((prev,child))\n",
    "            ### 老树的父节点的左子结点为原孩子的第一个\n",
    "            parent.left=head \n",
    "        \n",
    "        return rootNode\n",
    "        \t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        ## 1.边界条件\n",
    "        if not data:return None \n",
    "        ### 2.2叉树解码成N叉树\n",
    "        rootNode=Node(data.val,[])\n",
    "\n",
    "        q=deque([(rootNode,data)])\n",
    "\n",
    "        while q:\n",
    "            parent,curr=q.popleft()\n",
    "            first=curr.left \n",
    "            sub=first\n",
    "            while sub:\n",
    "                new=Node(sub.val,[])\n",
    "                parent.children.append(new)\n",
    "                q.append((new,sub))\n",
    "                sub=sub.right \n",
    "        \n",
    "        return rootNode\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, root):\n",
    "        if not root:\n",
    "           return None\n",
    "        rootNode= TreeNode(root.val)\n",
    "        q = collections.deque([(rootNode,root)])\n",
    "        while q:\n",
    "            pa,cur = q.popleft()\n",
    "            pre,head = None,None\n",
    "            for child in cur.children:\n",
    "                newNode = TreeNode(child.val)\n",
    "                if pre:\n",
    "                    pre.right = newNode\n",
    "                else:\n",
    "                    head = newNode\n",
    "                pre = newNode\n",
    "                q.append((newNode,child))\n",
    "            pa.left = head\n",
    "        return rootNode\n",
    "\n",
    "\n",
    "    def decode(self, data):\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "       # 应将缺省值设置为[]，而不是无，\n",
    "       # 否则它不会通过测试用例。\n",
    "        rootNode = Node(data.val, [])\n",
    "\n",
    "        q = collections.deque([(rootNode,data)])\n",
    "        \n",
    "\n",
    "        while q:\n",
    "            pa,cur = q.popleft()\n",
    "            first = cur.left\n",
    "            sib = first\n",
    "            while sib:\n",
    "                newNode = Node(sib.val,[])\n",
    "                pa.children.append(newNode)\n",
    "                q.append((newNode,sib))\n",
    "                sib = sib.right\n",
    "        return rootNode\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        rootNode = TreeNode(root.val)\n",
    "        queue = [(rootNode, root)]\n",
    "\n",
    "        while queue:\n",
    "            parent, cur = queue.pop(0)\n",
    "            prevBNode = None\n",
    "            headBNode = None\n",
    "            for child in cur.children:\n",
    "                newBNode = TreeNode(child.val)\n",
    "                if prevBNode:\n",
    "                    prevBNode.right = newBNode\n",
    "                else:\n",
    "                    headBNode = newBNode\n",
    "                prevBNode = newBNode\n",
    "                queue.append((newBNode, child))\n",
    "            parent.left = headBNode\n",
    "        return rootNode\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return None\n",
    "        \n",
    "        rootNode = Node(data.val, [])\n",
    "        queue = [(rootNode, data)]\n",
    "        while queue:\n",
    "            parent, cur = queue.pop(0)\n",
    "            firstchild = cur.left\n",
    "            sibling = firstchild\n",
    "\n",
    "            while sibling:\n",
    "                newNode = Node(sibling.val, [])\n",
    "                parent.children.append(newNode)\n",
    "                queue.append((newNode, sibling))\n",
    "                sibling = sibling.right\n",
    "        return rootNode\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Node') -> TreeNode:\n",
    "        if not root: return\n",
    "        res = TreeNode(root.val)\n",
    "        if root.children:\n",
    "            res.left = self.encode(root.children[0])\n",
    "        cur = res.left\n",
    "        for node in root.children[1:]:\n",
    "            cur.right = self.encode(node)\n",
    "            cur = cur.right\n",
    "        return res\n",
    "\n",
    "    # Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: TreeNode) -> 'Node':\n",
    "        if not data: return\n",
    "        res = Node(data.val, [])\n",
    "        cur = data.left\n",
    "        while cur:\n",
    "            res.children.append(self.decode(cur))\n",
    "            cur = cur.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "   def encode(self, root):\n",
    "       if not root:\n",
    "           return None\n",
    "\n",
    "       rootNode = TreeNode(root.val)\n",
    "       queue = deque([(rootNode, root)])\n",
    "\n",
    "       while queue:\n",
    "           parent, curr = queue.popleft()\n",
    "           prevBNode = None\n",
    "           headBNode = None\n",
    "           # 逐个遍历每个孩子\n",
    "           for child in curr.children:\n",
    "               newBNode = TreeNode(child.val)\n",
    "               if prevBNode:\n",
    "                   prevBNode.right = newBNode\n",
    "               else:\n",
    "                   headBNode = newBNode\n",
    "               prevBNode = newBNode\n",
    "               queue.append((newBNode, child))\n",
    "\n",
    "           # 使用parent的左侧节点中的第一个子节点\n",
    "           parent.left = headBNode\n",
    "\n",
    "       return rootNode\n",
    "\n",
    "\n",
    "   def decode(self, data):\n",
    "       if not data:\n",
    "           return None\n",
    "\n",
    "       # 应将缺省值设置为[]，而不是无，\n",
    "       # 否则它不会通过测试用例。\n",
    "       rootNode = Node(data.val, [])\n",
    "\n",
    "       queue = deque([(rootNode, data)])\n",
    "\n",
    "       while queue:\n",
    "           parent, curr = queue.popleft()\n",
    "\n",
    "           firstChild = curr.left\n",
    "           sibling = firstChild\n",
    "\n",
    "           while sibling:\n",
    "               # 注：孩子名单的初始值不应为None，这是线上评测机的预设。\n",
    "               newNode = Node(sibling.val, [])\n",
    "               parent.children.append(newNode)\n",
    "               queue.append((newNode, sibling))\n",
    "               sibling = sibling.right\n",
    "\n",
    "       return rootNode\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        rootNode = TreeNode(root.val)\n",
    "        if len(root.children) > 0:\n",
    "            firstchild = root.children[0]\n",
    "            rootNode.left = self.encode(firstchild)\n",
    "        \n",
    "        cur = rootNode.left\n",
    "        for i in range(1, len(root.children)):\n",
    "            cur.right = self.encode(root.children[i])\n",
    "            cur = cur.right\n",
    "        return rootNode\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return None\n",
    "        \n",
    "        rootNode = Node(data.val, [])\n",
    "        cur = data.left\n",
    "        while cur:\n",
    "            rootNode.children.append(self.decode(cur))\n",
    "            cur = cur.right\n",
    "        return rootNode\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None \n",
    "        newRoot = TreeNode(root.val)\n",
    "        queue = collections.deque([[root, newRoot]])\n",
    "        while queue:\n",
    "            cur, curNode = queue.popleft() \n",
    "            first = None \n",
    "            pre = None   \n",
    "            for child in cur.children:\n",
    "                new = TreeNode(child.val)\n",
    "                if not first:\n",
    "                    first = new \n",
    "                else:\n",
    "                    pre.right = new \n",
    "                pre = new \n",
    "                queue.append([child, new])\n",
    "            curNode.left = first \n",
    "        return newRoot\n",
    "                \n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':\n",
    "        if not data:\n",
    "            return None   \n",
    "        newRoot = Node(data.val, [])\n",
    "        queue = collections.deque([[data, newRoot]])\n",
    "        while queue:\n",
    "            cur, curNode = queue.popleft() \n",
    "            sibling = cur.left  \n",
    "            while sibling:\n",
    "                new = Node(sibling.val, [])\n",
    "                curNode.children.append(new)\n",
    "                queue.append([sibling, new])\n",
    "                sibling = sibling.right \n",
    "        return newRoot\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: 'Node') -> TreeNode:\n",
    "        def buildBinary(root,brothers):\n",
    "            if not root:\n",
    "                return None\n",
    "            head = TreeNode(root.val)\n",
    "            if root.children:\n",
    "                head.left = buildBinary(root.children[0],root.children[1:])\n",
    "            else:\n",
    "                head.left = None\n",
    "            if brothers:\n",
    "                head.right = buildBinary(brothers[0],brothers[1:]) \n",
    "            else:\n",
    "                head.right = None     \n",
    "            return head\n",
    "        head = buildBinary(root,[])\n",
    "        return head\n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: TreeNode) -> 'Node':\n",
    "        if not data: return None\n",
    "        if not data.left:\n",
    "            return Node(val=data.val,children=[])\n",
    "        children = []\n",
    "        curChild = data.left\n",
    "        while curChild:\n",
    "            children.append(self.decode(curChild))\n",
    "            curChild = curChild.right\n",
    "        return Node(val=data.val,children=children)\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\"\"\"\n",
    "from typing import Optional\n",
    "\n",
    "class Codec:\n",
    "    # Encodes an n-ary tree to a binary tree.\n",
    "    def encode(self, root: Optional['Node']) -> Optional['TreeNode']:\n",
    "        def dfs(node: 'Node'):\n",
    "            n = TreeNode(node.val)\n",
    "            if not node.children:\n",
    "                return n\n",
    "            n.left = dfs(node.children[0])\n",
    "            leaf = n.left\n",
    "            i = 1\n",
    "            while i < len(node.children):\n",
    "                leaf.right = dfs(node.children[i])\n",
    "                leaf = leaf.right\n",
    "                i += 1\n",
    "            return n\n",
    "        if root is None: return None\n",
    "        return dfs(root)\n",
    "        \n",
    "\t\n",
    "\t# Decodes your binary tree to an n-ary tree.\n",
    "    def decode(self, data: Optional['TreeNode']) -> Optional['Node']:\n",
    "        def traverse(treeNode: TreeNode, parent: TreeNode):\n",
    "            if treeNode is None: return\n",
    "            n = Node(treeNode.val, [])\n",
    "            parent.children.append(n)\n",
    "            traverse(treeNode.left, n)\n",
    "            traverse(treeNode.right, parent)\n",
    "        if data is None: return None\n",
    "        root = Node(0, [])\n",
    "        traverse(data, root)\n",
    "        return root.children[0]\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 脑筋急转弯\n",
    "    def encode(self, num: int) -> str:\n",
    "        return bin(num + 1)[3:]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        return bin(num+1)[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        return bin(num+1)[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        return bin(num+1)[3:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        return bin(num + 1)[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        return bin(num+1)[3:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        return bin(num+1)[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        num += 1\n",
    "        ans = \"\"\n",
    "        while num:\n",
    "            ans += str(num % 2)\n",
    "            num //= 2\n",
    "        ans = ans[::-1]\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        num += 1\n",
    "        stack = []\n",
    "        while num:\n",
    "            stack.append(str(num & 1))\n",
    "            num >>= 1\n",
    "        stack.pop()\n",
    "        return \"\".join(stack[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        num += 1\n",
    "        stack = []\n",
    "        while num:\n",
    "            stack.append(str(num & 1))\n",
    "            num >>= 1\n",
    "        stack.pop()\n",
    "        return \"\".join(stack[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return \"\"\n",
    "        n=num+1\n",
    "        return bin(n)[3:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "'''\n",
    "递归进行压缩，把s切分成两半，左边一半如果能够按照整倍数压缩，就进行压缩，先把左边一半变成最短的，\n",
    "然后递归处理右边一半，把两半都处理完之后的字符串拼接回来，最短的拼接字符串就是答案，判断能不能进行\n",
    "整倍数压缩的时候，问题转换为找串的重复子串问题\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    #  返回最短的以倍数压缩后的字符串，不能压缩返回原字符串\n",
    "    @lru_cache(typed=False)\n",
    "    def compress(self, s: str):\n",
    "        if s == '' or len(s) == 1:\n",
    "            return s\n",
    "\n",
    "        t = s + s\n",
    "        n = len(s)\n",
    "        ans = s\n",
    "\n",
    "        # 找重复子串位置\n",
    "        idx = t.find(s, 1)\n",
    "        if idx == n:\n",
    "            return ans\n",
    "\n",
    "        cnt = len(s) // idx\n",
    "        encode_str = self.encode(s[:idx])\n",
    "        ss = str(cnt) + '[' + encode_str + ']'\n",
    "        if len(ss) < len(ans):\n",
    "            ans = ss\n",
    "        return ans\n",
    "\n",
    "    @lru_cache(typed=False)\n",
    "    def encode(self, s: str) -> str:\n",
    "        #print(s)\n",
    "        if s == '' or len(s) == 1:\n",
    "            return s\n",
    "\n",
    "        ans = s\n",
    "        for i in range(0, len(s)):\n",
    "            ss = self.compress(s[:i+1]) + self.encode(s[i+1:])\n",
    "            if len(ss) < len(ans):\n",
    "                ans = ss\n",
    "        return ans\n",
    "\n",
    "# 作者：皓首不倦.GRH\n",
    "# 链接：https://leetcode.cn/problems/encode-string-with-shortest-length/solutions/194981/python-di-gui-ya-suo-zi-fu-chuan-shuang-100-by-hao/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def encode(self, s: str) -> str:\n",
    "        res = s\n",
    "        for i in range(1, len(s) + 1):\n",
    "            tmp = s[:i]\n",
    "            res = min(res, tmp + self.encode(s[i:]), key=len)\n",
    "            cnt = 1\n",
    "            j = i\n",
    "            while s[j:].find(tmp) == 0:\n",
    "                cnt += 1\n",
    "                j += len(tmp)\n",
    "                res = min(res, str(cnt) + \"[\" + self.encode(tmp) + \"]\" + self.encode(s[j:]), key=len)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        # 对当前考虑的字符串cur_str返回其最短编码\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur_str: str) -> str:\n",
    "            n = len(cur_str)\n",
    "            # 初始化结果，最差的情况就是不编码，直接返回原字符串\n",
    "            res = cur_str\n",
    "            # 编码的方式是将重复段用\"数量[重复段]\"的方式表达，那么就找重复段咯，\n",
    "            # 那重复段的长度肯定不能大于总长度的1/2吧，接下来对可能的重复段长度遍历\n",
    "            for i in range(1, 1 + n // 2):\n",
    "                temp = cur_str[:i]\n",
    "                # 先考虑直接把第一个取出的片段以及剩下的片段递归地找一下他们的编码，拼起来\n",
    "                cur_candi = dfs(temp) + dfs(cur_str[i:])\n",
    "                # 只要长度比目前找到的答案小，就更新一下答案\n",
    "                if len(cur_candi) < len(res):\n",
    "                    res = cur_candi\n",
    "\n",
    "                # 接下来，每有一个重复段，就把重复段拼一起，并把剩下的部分递归地找一下编码\n",
    "                j = i\n",
    "                while cur_str[j:j + i] == temp:\n",
    "                    j += i\n",
    "                    # (j // i)即是当前重复段的重复数量，dfs(temp)返回了对重复片段的编码，\n",
    "                    # dfs(cur_str[j:])则对剩下的部分进行编码\n",
    "                    cur_candi = str(j // i) + '[' + dfs(temp) + ']' + dfs(cur_str[j:])\n",
    "                    if len(cur_candi) < len(res):\n",
    "                        res = cur_candi\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        ans = s\n",
    "        n = len(s)\n",
    "        f = [['*'] * n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i, n):\n",
    "                if j - i >= 3:\n",
    "                    t = s[i:j+1]\n",
    "                    m, mn = len(t), t\n",
    "                    idx = (t + t).index(t, 1)\n",
    "                    if idx!= m:\n",
    "                        cp = f[i][i + idx - 1]\n",
    "                        mn = f'{m//idx}[{cp}]'\n",
    "                    for k in range(i, j):\n",
    "                        if len(f[i][k]) + len(f[k+1][j]) < len(mn):\n",
    "                            mn = f[i][k] + f[k + 1][j]\n",
    "                    f[i][j] = mn\n",
    "                else:\n",
    "                    f[i][j] = s[i:j+1]\n",
    "        return f[0][n-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        f = [['']*n for _ in range(n)]\n",
    "        for L in range(1,n + 1):\n",
    "            for i in range(n - L + 1):\n",
    "                j = i + L - 1\n",
    "                f[i][j] = s[i:i + L]\n",
    "                if L >= 5:\n",
    "                    t = f[i][j] + f[i][j]\n",
    "                    p = t.find(f[i][j],1)\n",
    "                    if p < L:\n",
    "                        f[i][j] = str(L//p) + '['+f[i][i+ p - 1] +']'\n",
    "                        continue\n",
    "                    for k in range(i,j):\n",
    "                        if len(f[i][k]) + len(f[k + 1][j]) < len(f[i][j]):\n",
    "                            f[i][j] = f[i][k] + f[k + 1][j]\n",
    "                \n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        dp = [['' for _ in range(n)] for _ in range(n)]\n",
    "        for l in range(1, n + 1):\n",
    "            for i in range(n - l + 1):\n",
    "                j = i + l - 1 \n",
    "                dp[i][j] = s[i : j + 1]\n",
    "                sub = s[i : j + 1]\n",
    "                if l >= 5:\n",
    "                    p = (sub + sub).index(sub, 1)\n",
    "                    if p <= len(sub):\n",
    "                        dp[i][j] = str(l // p) + '[' + dp[i][i + p - 1] + ']'\n",
    "                for k in range(i, j):\n",
    "                    if len(dp[i][j]) > len(dp[i][k]) + len(dp[k + 1][j]):\n",
    "                        dp[i][j] = dp[i][k] + dp[k + 1][j]\n",
    "        \n",
    "        for l in range(1, n + 1):\n",
    "            for i in range(n - l + 1):\n",
    "                j = i + l - 1 \n",
    "                sub = s[i : j + 1]\n",
    "                dp[i][j] = sub\n",
    "                if l >= 5:\n",
    "                    p = (sub + sub).index(sub, 1)\n",
    "                    if p < l:\n",
    "                        dp[i][j] = str(l // p) + '[' + dp[i][i + p - 1] + ']'\n",
    "                for k in range(i, j):\n",
    "                    if len(dp[i][k]) + len(dp[k + 1][j]) < len(dp[i][j]):\n",
    "                        dp[i][j] = dp[i][k] + dp[k + 1][j]\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        dp = {}\n",
    "        for step in range(1, len(s) + 1):\n",
    "            for j in range(len(s) - step + 1):\n",
    "                tmp = s[j:j + step]\n",
    "                dp.setdefault(tmp, tmp)\n",
    "                if len(dp[tmp]) < len(tmp):continue\n",
    "                loc = (tmp + tmp).find(tmp, 1)\n",
    "                if loc < len(tmp):\n",
    "                    dp.setdefault(tmp[:loc], tmp[:loc])\n",
    "                    dp[tmp] = min(dp[tmp], str(len(tmp) // loc) + \"[\" + dp[tmp[:loc]] + \"]\", key=len)\n",
    "\n",
    "                \n",
    "                for k in range(1, len(tmp)):\n",
    "                    left = dp.setdefault(tmp[:k], tmp[:k])\n",
    "                    right = dp.setdefault(tmp[k:], tmp[k:])\n",
    "                    dp[tmp] = min(dp[tmp], left + right, key=len)\n",
    "        return dp[s]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        dt=dict()\n",
    "        @cache\n",
    "        def f(st):\n",
    "            # if st in dt:\n",
    "            #     return dt[st]\n",
    "            l=len(st)\n",
    "            nexl=l\n",
    "            nexst=st\n",
    "            for k in range(1,l//2+1):\n",
    "                \n",
    "                if l%k==0:\n",
    "                    ct=l//k\n",
    "                    pre=st[0:k]\n",
    "                    if pre*ct==st:\n",
    "\n",
    "                        # print(\"!!!st:\",st,\"pre:\",pre)\n",
    "                        nst=str(ct)+'['+f(pre)+']'\n",
    "                        nl=len(nst)\n",
    "                        if nl<nexl:\n",
    "                            nexl=nl\n",
    "                            nexst=nst\n",
    "            for k in range(1,l):\n",
    "                left=st[0:k]\n",
    "                right=st[k:]\n",
    "                # print(\"left:\",left,\"right:\",right)\n",
    "                dgres=f(left)+f(right)\n",
    "                if len(dgres)<nexl:\n",
    "                    nexst=dgres\n",
    "                    nexl=len(dgres)\n",
    "            # dt[st]=nexst\n",
    "            return nexst\n",
    "        return f(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(s):\n",
    "            n=len(s)\n",
    "            res=s\n",
    "            if n<5:return s #为什么是小于5\n",
    "            t=s+s \n",
    "            idx=t.find(s,1)#从t的索引为1处开始查找是否有s \n",
    "            if idx<n:\n",
    "                cnt=n//idx\n",
    "                res=str(cnt)+'['+dfs(s[:idx])+']'\n",
    "            for i in range(1,len(s)):\n",
    "                left,right=dfs(s[:i]),dfs(s[i:])\n",
    "                res=min(res,left+right,key=len)\n",
    "            return res \n",
    "        return dfs(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        # # sol 1\n",
    "        # # 对当前考虑的字符串cur_str返回其最短编码\n",
    "        # @functools.lru_cache(None)\n",
    "        # def dfs(cur_str: str) -> str:\n",
    "        #     n = len(cur_str)\n",
    "        #     # 初始化结果，最差的情况就是不编码，直接返回原字符串\n",
    "        #     res = cur_str\n",
    "        #     # 编码的方式是将重复段用\"数量[重复段]\"的方式表达，那么就找重复段咯，\n",
    "        #     # 那重复段的长度肯定不能大于总长度的1/2吧，接下来对可能的重复段长度遍历\n",
    "        #     for i in range(1, 1 + n // 2):\n",
    "        #         temp = cur_str[:i]\n",
    "        #         # 先考虑直接把第一个取出的片段以及剩下的片段递归地找一下他们的编码，拼起来\n",
    "        #         cur_candi = dfs(temp) + dfs(cur_str[i:])\n",
    "        #         # 只要长度比目前找到的答案小，就更新一下答案\n",
    "        #         if len(cur_candi) < len(res):\n",
    "        #             res = cur_candi\n",
    "\n",
    "        #         # 接下来，每有一个重复段，就把重复段拼一起，并把剩下的部分递归地找一下编码\n",
    "        #         j = i\n",
    "        #         while cur_str[j:j + i] == temp:\n",
    "        #             j += i\n",
    "        #             # (j // i)即是当前重复段的重复数量，dfs(temp)返回了对重复片段的编码，\n",
    "        #             # dfs(cur_str[j:])则对剩下的部分进行编码\n",
    "        #             cur_candi = str(j // i) + '[' + dfs(temp) + ']' + dfs(cur_str[j:])\n",
    "        #             if len(cur_candi) < len(res):\n",
    "        #                 res = cur_candi\n",
    "        #     print(res)\n",
    "        #     return res\n",
    "\n",
    "        # return dfs(s)\n",
    "\n",
    "        # sol 2 运用了S+S\n",
    "        @lru_cache(None)\n",
    "        def compress(s):\n",
    "            n = len(s)\n",
    "            res = s\n",
    "            if n<5:return s\n",
    "            t = s+s\n",
    "            #t.find(s,1)从t的索引1处找是否有s\n",
    "            index = t.find(s,1)\n",
    "            if index<n:\n",
    "                cnt = n//index\n",
    "                res = str(cnt)+'['+compress(s[:index])+']'\n",
    "\n",
    "            for i in range(1,len(s)):\n",
    "                left = compress(s[:i])\n",
    "                right = compress(s[i:])\n",
    "                #注意这个key = len\n",
    "                res = min(res,left+right,key = len)            \n",
    "            return res\n",
    "\n",
    "        return compress(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_min_ans(s1: str):\n",
    "            if len(s1) < 5:\n",
    "                return s1\n",
    "            ori_s = s1\n",
    "            for i in range(1, len(s1)):\n",
    "                seed_part = s1[:i]\n",
    "                idx = 0\n",
    "                for j in range(2, 999):\n",
    "                    wanted = seed_part * j\n",
    "                    if s1.startswith(wanted) is False:\n",
    "                        break\n",
    "                    idx += 1\n",
    "                total = seed_part * (idx+1)\n",
    "                if len(total) >= 5:\n",
    "                    ll1 = str(idx+1) + '[' + get_min_ans(seed_part) +']'\n",
    "                    x1 = s1[len(total):]\n",
    "                    rpart = get_min_ans(x1)\n",
    "                    ori_s = min(ori_s, ll1 + rpart, key=len)\n",
    "                lx = s1[:i]\n",
    "                rx = s1[i:]\n",
    "                ori_s = min(ori_s, get_min_ans(lx) + get_min_ans(rx), key=len)\n",
    "            return ori_s\n",
    "\n",
    "        ret = get_min_ans(s)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#编码最短长度的字符串,记忆化搜索，区间dp，输入：s = \"aaa\"输出：\"aaa\"输入：s = \"aaaaa\"输出：\"5[a]\"输入：s = \"aabcaabcd\"输出：\"2[aabc]d\"\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dfs(s):\n",
    "            n,res=len(s),s\n",
    "            if n<5:return s #为什么是小于5\n",
    "            t=s+s \n",
    "            idx=t.find(s,1)#从t的索引为1处开始查找是否有s \n",
    "            if idx<n:\n",
    "                cnt=n//idx\n",
    "                res=str(cnt)+'['+dfs(s[:idx])+']'\n",
    "            for i in range(1,len(s)):\n",
    "                left,right=dfs(s[:i]),dfs(s[i:])\n",
    "                res=min(res,left+right,key=len)\n",
    "            return res \n",
    "        return dfs(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_min_ans(s1: str):\n",
    "            if len(s1) < 5:\n",
    "                return s1\n",
    "            ori_s = s1\n",
    "            for i in range(1, len(s1)):\n",
    "                seed_part = s1[:i]\n",
    "                idx = 0\n",
    "                for j in range(2, 999):\n",
    "                    wanted = seed_part * j\n",
    "                    if s1.startswith(wanted) is False:\n",
    "                        break\n",
    "                    idx += 1\n",
    "                total = seed_part * (idx+1)\n",
    "                if len(total) >= 5:\n",
    "                    ll1 = str(idx+1) + '[' + get_min_ans(seed_part) +']'\n",
    "                    x1 = s1[len(total):]\n",
    "                    rpart = get_min_ans(x1)\n",
    "                    ori_s = min(ori_s, ll1 + rpart, key=len)\n",
    "                lx = s1[:i]\n",
    "                rx = s1[i:]\n",
    "                ori_s = min(ori_s, get_min_ans(lx) + get_min_ans(rx), key=len)\n",
    "            return ori_s\n",
    "\n",
    "        ret = get_min_ans(s)\n",
    "        return ret\n",
    "\n",
    "a = Solution()\n",
    "print(a.encode(s = \"aabcccccddd\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    best_code = {}\n",
    "\n",
    "    def encode(self, s: str) -> str:\n",
    "        if s in Solution.best_code:\n",
    "            return Solution.best_code[s]\n",
    "        if len(s) <= 4:\n",
    "            Solution.best_code[s] = s\n",
    "            return s\n",
    "\n",
    "        cur_best = s\n",
    "\n",
    "        # multiple times\n",
    "        possible_L = []\n",
    "        for L in range(1, len(s)//2+1):\n",
    "            if len(s) % L != 0: continue\n",
    "            s_rec = s[:L] * (len(s) // L)\n",
    "            if s_rec == s:\n",
    "                possible_L.append(L)\n",
    "                best_sub = self.encode(s[:L])\n",
    "                if len(cur_best) > len(str(len(s) // L)) + 2 + len(best_sub):\n",
    "                    cur_best = str(len(s) // L) + '[' + best_sub + ']'\n",
    "        if possible_L:\n",
    "            Solution.best_code[s] = cur_best\n",
    "            return cur_best\n",
    "\n",
    "        # split into two\n",
    "        for i in range(1, len(s)):\n",
    "            best_left   = self.encode(s[:i])\n",
    "            best_right  = self.encode(s[i:])\n",
    "            if len(cur_best) > len(best_left) + len(best_right):\n",
    "                cur_best = best_left + best_right\n",
    "        Solution.best_code[s] = cur_best\n",
    "        return cur_best\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        d = {}\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                dp[i][j] = j - i + 1\n",
    "                d[(i, j)] = s[i:j + 1]\n",
    "        for delta in range(2, n):\n",
    "            for j in range(delta, n):\n",
    "                i = j - delta\n",
    "                cur_s = s[i:j + 1]\n",
    "                for k in range(i, j):\n",
    "                    if dp[i][k] + dp[k + 1][j] < dp[i][j]:\n",
    "                        dp[i][j] = dp[i][k] + dp[k + 1][j]\n",
    "                        d[(i, j)] = d[(i, k)] + d[(k + 1, j)]\n",
    "                for k in range(1, int((delta + 2) ** 0.5) + 1):\n",
    "                    q, r = divmod(delta + 1, k)\n",
    "                    if r > 0:\n",
    "                        continue\n",
    "                    for k1, k2 in [[k, q], [q, k]]:\n",
    "                        if k2 == 1:\n",
    "                            continue\n",
    "                        if cur_s == s[i:i + k1] * k2:\n",
    "                            cur_length = 2 + len(str(k2)) + dp[i][i + k1 - 1]\n",
    "                            if cur_length < dp[i][j]:\n",
    "                                dp[i][j] = cur_length\n",
    "                                d[(i, j)] = str(k2) + '[' + d[(i, i + k1 - 1)] + ']'\n",
    "        return d[(0, n - 1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "        dt=dict()\n",
    "        def f(st):\n",
    "            if st in dt:\n",
    "                return dt[st]\n",
    "            l=len(st)\n",
    "            nexl=l\n",
    "            nexst=st\n",
    "            for k in range(1,l//2+1):\n",
    "                \n",
    "                if l%k==0:\n",
    "                    ct=l//k\n",
    "                    pre=st[0:k]\n",
    "                    if pre*ct==st:\n",
    "\n",
    "                        # print(\"!!!st:\",st,\"pre:\",pre)\n",
    "                        nst=str(ct)+'['+f(pre)+']'\n",
    "                        nl=len(nst)\n",
    "                        if nl<nexl:\n",
    "                            nexl=nl\n",
    "                            nexst=nst\n",
    "            for k in range(1,l):\n",
    "                left=st[0:k]\n",
    "                right=st[k:]\n",
    "                # print(\"left:\",left,\"right:\",right)\n",
    "                dgres=f(left)+f(right)\n",
    "                if len(dgres)<nexl:\n",
    "                    nexst=dgres\n",
    "                    nexl=len(dgres)\n",
    "            dt[st]=nexst\n",
    "            return nexst\n",
    "        return f(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def encode(self, s: str) -> str:\n",
    "        res = s\n",
    "        if len(s) <= 4:\n",
    "            return res\n",
    "\n",
    "        # lc459 寻找是否有循环节 period就是循环节的长度\n",
    "        period = (s + s).find(s, 1, -1)\n",
    "\n",
    "        # 有循环节\n",
    "        if period not in (-1, 0):\n",
    "            res = str(len(s) // period) + f'[{self.encode(s[:period])}]'\n",
    "\n",
    "        # 枚举分割点\n",
    "        for i in range(1, len(s)):\n",
    "            left = self.encode(s[:i])\n",
    "            right = self.encode(s[i:])\n",
    "            res = min(res, left + right, key=len)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, s: str) -> str:\n",
    "\n",
    "        @cache\n",
    "        def dfs(left,right):\n",
    "            ret = s[left:right+1] \n",
    "            if len(ret)<=4:\n",
    "                return ret\n",
    "            for step in range(1,(right-left+1)//2+1):\n",
    "                if (right-left+1)%step!=0:continue\n",
    "                if all( s[c:c+step] == s[left:left+step] for c in range(left+step,right+2-step,step)):\n",
    "                    tmp = str( (right-left+1)//step )+'['+ dfs(left,left+step-1) +']'\n",
    "                    if len( tmp )<len(ret):\n",
    "                        ret = tmp \n",
    "            \n",
    "            for i in range(left,right):\n",
    "                ret1 = dfs(left,i)\n",
    "                ret2 = dfs(i+1,right)\n",
    "                if len(ret1)+len(ret2)< len(ret):\n",
    "                    ret = ret1+ret2\n",
    "            return ret\n",
    "        \n",
    "        return dfs(0,len(s)-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
